配点 : $300$ 点

問題文

長さ $N$ の整数列 $A \sim = \sim A_0, \sim A_1, \sim ..., \sim A_{N - 1}$ があります。

$A$ を $K$ 回繰り返した長さ $K \times N$ の整数列を $B$ とします。たとえば $A \sim = \sim 1, \sim 3, \sim 2$、$K \sim = \sim 2$ のとき、 $B \sim = \sim 1, \sim 3, \sim 2, \sim 1, \sim 3, \sim 2$ です。

$B$ の転倒数を $10^9 + 7$ で割った余りを求めてください。

ここで $B$ の転倒数は、整数の順序対 $(i, \sim j) \sim (0 \leq i < j \leq K \times N - 1)$ であって $B_i > B_j$ を満たすものの個数として定義されます。

制約

• 入力は全て整数である。
• $1 \leq N \leq 2000$
• $1 \leq K \leq 10^9$
• $1 \leq A_i \leq 2000$

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$

$A_0$ $A_1$ $...$ $A_{N - 1}$

出力

$B$ の転倒数を $10^9 + 7$ で割った余りを出力せよ。

2 2
2 1

3

このケースでは $B \sim = \sim 2, \sim 1, \sim 2, \sim 1$ です。

• $B_0 > B_1$
• $B_0 > B_3$
• $B_2 > B_3$

であり、$B$ の転倒数は $3$ です。

3 5
1 1 1

0

$A$ は同じ数を複数含むこともあります。

10 998244353
10 9 8 7 5 6 3 4 2 1

185297239

$10^9 + 7$ で割った余りを出力することに注意してください。