题目描述

有 $n$ 个标靶排成一行，第 $i$ 个标靶的高度为 $a_i$。

炮弹从左侧以等概率随机高度 $h$（$1 \leq h \leq m$）发射，水平向右移动。当炮弹遇到第一个未被摧毁的标靶且 $h \leq$ 该标靶高度时，炮弹和标靶同时被摧毁。重复发射炮弹，直到所有标靶被摧毁。

目标是调整标靶的排列顺序，使得摧毁所有标靶的期望发射次数 $E$ 最大。输出 $E_{\text{max}} \mod (10^9 + 7)$。

输入格式

第一行包含两个正整数 $n$ 和 $m$，表示标靶数和最大炮弹高度。

第二行包含 $n$ 个整数 $a_1,a_2,..., a_n$，表示标靶高度。

输出格式

一行一个整数，表示期望的最大值 $E_{\text{max}} \mod (10^9 + 7)$。

2 2
1000 1

3

数据范围

$1 \leq n \leq 10^6$，$1 \leq m \leq 10^9$，$1 \leq a_i \leq 10^9$