说明

时间限制：1 Sec 内存限制：256 MB 输入文件：growth.in 输出文件：growth.out

小明同学每天坚持练习竞技编程，过去 $N$ 天里他参加了比赛并记录了每天的得分。

设得分序列为 $A=\{A_1,A_2,...,A_N\}$，小明同学将 $N$ 天的「成长数 $g(A)$」定义为满足 $\max\{A_1,A_2,...,A_i\} < A_{i+1}$ 的 $0 \le i \le N-1$ 的数量。

注意：规定空集的最大值 $\max(\emptyset)=-\infty$（即第 $1$ 天一定算作“成长”）。

例如，序列 $A = \{1,2,1,2,4\}$ 的成长数为 $3$（需注意第 $1$ 天也判定为“成长”）。

某天因意外事故，得分记录的日期丢失了。虽然已知得分的集合（允许重复）为 $\{S_1,S_2,...,S_N\}$，但原始顺序已无法确认。

也就是说，原始得分序列 $\{A_1,A_2,...,A_N\}$ 可表示为 $A_i = S_{p_i}$（其中 $p$ 是 $\{1,2,...,N\}$ 的一个排列）。

下文记 $S(p):=\{S_{p_1}, S_{p_2},...,S_{p_N}\}$。

为了估算自己的成长程度，小明同学想知道：对 $\{1,2,...,N\}$ 的所有排列 $p$，得分函数 $\mathrm{SCORE}(p)=g(S(p)) \times B^{g(S(p))}$ 的总和。其中 $B$ 是给定的正整数。

你的任务是帮小明同学解决这个问题。由于答案可能极大，需输出答案对 $10^9+7$ 取模的结果。

输入格式

第一行：两个整数 $N$（得分集合 $S$ 的大小）和 $B$（得分函数中的参数），以空格分隔；

第二行：得分集合 $S$ 的 $N$ 个元素，以空格分隔。

输出格式

输出所有排列 $p$ 对应的 $\mathrm{SCORE}(p)$ 之和对 $10^9+7$ 取模的结果，最后需换行。

样例

样例 1

3 2
0 1 2

52

样例说明：

各排列对应的得分序列及计算结果如下：

- $A=\{0,1,2\}$：$g(A)=3$，$\mathrm{SCORE}=3\times 2^3 = 24$

- $A=\{0,2,1\}$：$g(A)=2$，$\mathrm{SCORE}=2\times 2^2 = 8$

- $A=\{1,0,2\}$：$g(A)=2$，$\mathrm{SCORE}=2\times 2^2 = 8$

- $A=\{1,2,0\}$：$g(A)=2$，$\mathrm{SCORE}=2\times 2^2 = 8$

- $A=\{2,0,1\}$：$g(A)=1$，$\mathrm{SCORE}=1\times 2^1 = 2$

- $A=\{2,1,0\}$：$g(A)=1$，$\mathrm{SCORE}=1\times 2^1 = 2$

总和：$24+8+8+8+2+2=52$

样例 2

2 1
1 1

2

样例说明：

排列 $p = \{0,1\}$ 和 $p = \{1,0\}$ 对应的得分序列均为 $A=\{1,1\}$，但需视为两个不同的排列分别计数。

样例 3

6 548438800
2 3 3 1 0 2

140476412

数据范围

对于 50% 的数据，$N \le 10$。

对于 100% 的数据，$1 \le N \le 2\times 10^5$，$1 \le B < 10^9+7$，$0 \le S_i < N$。