No.829 成長関数インフレ中

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 11
作問者 : PachicobuePachicobue / テスター : koprickykopricky
1 ProblemId : 2596 / 出題時の順位表

問題文

青木くんは競技プログラミングの精進を毎日行っており,これまでに$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$ とします。
例えば $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$ で割った余りを教えてあげて下さい。

入力

$N\ B$
$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 \lt 10^9+7$
  • $0 \le S_i \lt N$
  • 入力は全て整数である。

出力

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

サンプル

サンプル1
入力
3 2
0 1 2
出力
52

各順列に対応する得点順は

  • $A=\{0,1,2\} : g(A)=3, \mathrm{SCORE}=3\times 2^3$
  • $A=\{0,2,1\} : g(A)=2, \mathrm{SCORE}=2\times 2^2$
  • $A=\{1,0,2\} : g(A)=2, \mathrm{SCORE}=2\times 2^2$
  • $A=\{1,2,0\} : g(A)=2, \mathrm{SCORE}=2\times 2^2$
  • $A=\{2,0,1\} : g(A)=1, \mathrm{SCORE}=1\times 2^1$
  • $A=\{2,1,0\} : g(A)=1, \mathrm{SCORE}=1\times 2^1$
で、総和は$24+8+8+8+2+2=52$となります。

サンプル2
入力
2 1
1 1
出力
2

順列$p = \{0,1\}, \{1,0\}$で得点数列は同じ$A=\{1,1\}$となりますが、区別して数えることに注意して下さい。

サンプル3
入力
6 548438800
2 3 3 1 0 2
出力
140476412
提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。