Inversions of all permutations
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Amy asks Mr. B  problem C. Please help Mr. B to solve the following problem.

Given an array ai with length n, and a base b.

For each permutation {ri} of {ai}, we count the number of inversions as t({ri}).

Please calculate

As the answer might be very large, please output it modulo 1000000007.

输入描述:

The first line contains n, b (n <= 100000, 1 <= b <= 1000000000).
The second line contains n integers, which are ai (0 <= ai <= 100000).

输出描述:

Output the answer in one line.

As the answer might be very large, please output it modulo 1000000007.
示例1

输入

复制 
3 10
1 2 3

输出

复制 
1221

说明

There are 6 permutations. The number of inversions are 0, 1, 1, 2, 2, 3.
示例2

输入

复制 
4 10
1 1 2 2

输出

复制 
11211

说明

There are 6 permutations. The number of inversions are 0, 1, 2, 2, 3, 4.

If there are duplicate integers in {ai}, the number of permutations are less than the factorial of n(n!).
示例3

输入

复制 
10 10
1 2 3 4 5 6 7 8 9 10

输出

复制 
291457966

说明

Don't forget to mod 1000000007.