1638. 计数排序(使用C/C++)

计下标从 1 开始。有 n 个取值范围在 [1, m] 的整数 a_i。请将它们升序排序,设排序后数组为 b 。为避免输出过长,请输出: \left(\sum_{i=1}^ni\cdot b_i\right)\bmod (10^9+7)

输入

输入一行两个整数 n,m(1\le n,m\le10^7)

接下来输入一行 n 个整数 a_i(1\le a_i\le m)

输出

输出一个整数代表计算结果

样例

标准输入 复制文本
10 3
1 2 3 2 2 3 3 1 3 3
标准输出 复制文本
147

提示

请不要使用 std::sort 水过这道题qwq

提示: x\times y\bmod p 要开 long long

// 本题是先修班用题,属于算法竞赛题。因此,设计上本题只能使用 C/C++ 通过,Python/Java 可能无法过题。且请使用 scanf 等快速的读入方式。

登录以提交代码。
单点时限 3 秒
内存限制 128 MB
提交 3010
通过 589