分数: 300 点
问题陈述
我们有一系列 N 整数 A~=~A_0,~A_1,~...,~A_{N - 1}.
让 B 是一系列 K \times N 通过连接获得的整数 K 副本 A。例如,如果 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.
约束
- 输入中的所有值都是整数。
- 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.
示例输入 1
2 2 2 1
示例输出 1
3
在这种情况下, B~=~2,~1,~2,~1。我们有:
- B_0 > B_1
- B_0 > B_3
- B_2 > B_3
因此,反转数 B is 3.
示例输入 2
3 5 1 1 1
示例输出 2
0
A 可能包含多次出现的相同数字。
示例输入 3
10 998244353 10 9 8 7 5 6 3 4 2 1
示例输出 3
185297239
请务必打印输出模数 小于或等于 10^9 + 7.