問題文

青木くんは競技プログラミングの精進を毎日行っており，これまでに$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(\mathrm{\varnothing })=-\mathrm{\infty }$ とします。
例えば $A=\{1,2,1,2,4\}$ の成長数は3です(1日目にも「成長した」とすることに注意して下さい)。

ある日不慮の事故で得点記録の日付が消えてしまい、得点の集合(重複を許す)が $\{S_1,S_2,...,S_N\}$ であることは分かるものの、 元の順番がわからなくなりました。
つまり各日の得点数列 $\{A_1,A_2,...,A_N\}$ は、$\{1,2,..,,N\}$ の順列 $p$ を用いて $A_i=S_{p_i}$ と表せることが分かっています．
以下， $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$ で割った余りを教えてあげて下さい。

入力

$NB$
$S_1{S}_2{S}_3\dots S_N$

1行目に得点集合 $S$ の大きさ $N$ 、スコア関数の定義に関わる値 $B$ が空白区切りで与えられます。
2行目に得点集合 $S$ の要素が空白区切りで与えられます。

制約

• $1\le N\le 2\times {10}^5$
• $1\le B<{10}^9+7$
• $0\le S_i<N$
• 入力は全て整数である。

出力

$\{1,2,...,N\}$ の順列 $p$ に対する $\mathrm{SCORE}(p)=g(S(p))\times B^{g(S(p))}$ の総和を${10}^9+7$で割った余りを一行に出力して下さい。
最後に改行して下さい。

サンプル

3 2
0 1 2

52

2 1
1 1

2

6 548438800
2 3 3 1 0 2

140476412