No.1259 スイッチ
タグ : / 解いたユーザー数 89
作問者 : 👑
PCTprobability
/ テスター :
penguinman
問題文
$N$ 個のスイッチと長さ $N$ の数列 $A$ があり、各スイッチには $1,2,...N$ の番号がついています。 また、任意の $i (1 \le i \le N)$ に対して $1 \le A_i \le N$ が成り立ちます。
全てのスイッチは ON か OFF のどちらかであり、初めはスイッチ $1$ だけが ON になっていて、他は全て OFF になっています。 $1$ 回の操作では、ON になっているスイッチ $i$ を選び押します。するとスイッチ $i$ は OFF になり、スイッチ $A_i$ が ON になります。 $K$ 回操作をした後、スイッチ $M$ だけが ON になっている状態になりました。
この時、数列 $A$ としてあり得るものは何通りあるでしょうか。 ただし答えは非常に大きくなることがあるので、$1000000007=10^9+7$ で割った余りを出力してください。
入力
$N$ $K$ $M$
- $1 \le M \le N \le 10^6$
- $1 \le K \le 10^{18}$
- 入力は全て整数である。
出力
最後に改行してください。
サンプル
サンプル1
入力
3 1 1
出力
9
$A_1=1$ であれば他の要素はいくつでもいいので、$3^2=9$ 通りです。 具体的には $A=\{1,2,1\}$ などが当てはまります。
サンプル2
入力
1000 1000 1000
出力
10507954
$1000000007$ で割った余りを出力してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。