問題一覧 > 通常問題

No.1259 スイッチ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 57
作問者 : PCTprobabilityPCTprobability / テスター : penguinmanpenguinman
9 ProblemId : 5012 / 出題時の順位表
問題文最終更新日: 2020-10-13 16:18:06

問題文

$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もしくは右上の雲マークをクリックしてアカウントを作成してください。