permutation difference sum

2 secs 1024 MB
first_vil

問題文


長さ の数列 が与えられます。同じ要素を区別する並べ替え 通りすべてに対して隣接項の差の絶対値の総和を考え、それらの総和を で割った余りを答えてください。

制約


入力



出力


答えを出力せよ。

入力例1

3
10 3 5
出力例1

56
入力例2

10
81 98 49 80 26 57 69 80 87 97
出力例2

849139200

提出


Go (1.14)