题目描述

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

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

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

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

输入格式

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

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

输出格式

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

题目大意

给你一个长度为 $N$ 的数组 $A$，其中元素为 $A_0 \sim A_{n-1}$。

使长度为 $N\times K$ 数组 $B$，为 $K$ 个 $A$ 首尾相连而成。

求 $B$ 中逆序对的数目 $\bmod\;10^9+7$。

另外，样例 $2$ 并非没有输出，输出应为 $0$。

2 2
2 1

3

3 5
1 1 1

0

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

185297239

提示

制約

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

Sample Explanation 1

このケースでは $B~=~2,~1,~2,~1$ です。 - $B_0\ >\ B_1$ - $B_0\ >\ B_3$ - $B_2\ >\ B_3$ であり、$B$ の転倒数は $3$ です。

Sample Explanation 2

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

Sample Explanation 3

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