AT_jsc2019_qual_b.Kleene Inversion

有一个长度为 $N$ 的整数序列 $A = A_0, A_1, \ldots, 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$ 的逆序对数定义为满足 $0 \leq i < j \leq K \times N - 1$ 且 $B_i > B_j$ 的整数对 $(i, j)$ 的个数。

输入以如下格式从标准输入读入。

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

输出 $B$ 的逆序对数对 $10^9 + 7$ 取模的结果。

限制条件

• 所有输入均为整数。
• $1 \leq N \leq 2000$
• $1 \leq K \leq 10^9$
• $1 \leq A_i \leq 2000$

样例解释 1

在此样例中，$B = 2, 1, 2, 1$。

• $B_0 > B_1$
• $B_0 > B_3$
• $B_2 > B_3$
  因此，$B$ 的逆序对数为 $3$。

样例解释 2

$A$ 中可以包含多个相同的数。

样例解释 3

请注意输出时要对 $10^9 + 7$ 取模。

由 ChatGPT 4.1 翻译