← 返回题目列表

AtCoder · jsc2019_qual_b

B. 克莱恩反演

中文机器翻译题面 查看原题

分数: 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.