Problem Description

There is an integer sequence $ A = A_0, A_1, ..., A_{N - 1} $ of length $ N $.

Let $ B $ be the integer sequence of length $K \times N$ obtained by repeating $ A $ $ K $ times. For example, when $ A = 1, 3, 2 $ and $ K = 2 $, $ B = 1, 3, 2, 1, 3, 2 $.

Find the inversion number of $ B $ modulo $ 10^9 + 7 $.

The inversion number of $ B $ is defined as the number of pairs of integers $ (i, j) $ (where $0 \leq i < j \leq K \times N - 1$) such that $ B_i > B_j $.

Input Format

The input is given from the standard input in the following format:

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

Output Format

Output the inversion number of $ B $ modulo $ 10^9 + 7 $.

Sample Input and Output

Sample Input #1

2 2
2 1

Sample Output #1

3

Sample Input #2

3 5
1 1 1

Sample Output #2

0

Sample Input #3

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

Sample Output #3

185297239

Notes/Hints

Constraints

• All input values are integers.
• $1 \leq N \leq 2000$
• $1 \leq K \leq 10^9$
• $1 \leq A_i \leq 2000$

Sample Explanation 1

In this case, $ B = 2, 1, 2, 1 $. - $ B_0 > B_1 $ - $ B_0 > B_3 $ - $ B_2 > B_3 $ Thus, the inversion number of $ B $ is $ 3 $.

Sample Explanation 2

$ A $ may contain multiple identical numbers.

Sample Explanation 3

Be sure to output the result modulo $ 10^9 + 7 $.

见题面 Input 部分

见题面 Output 部分