No.1259 Switches
タグ : / 解いたユーザー数 89
作問者 :
PCTprobability
/ テスター :
penguinman
Problem Statement
There are $N$ switches and a sequence $A$ of length $N$. The switches are numbered $1,2,...N$. Also, $1 \le A_i \le N$ holds for every $i (1 \le i \le N)$.
Each switch is either ON or OFF. Initially, only switch $1$ is ON and all the others are OFF. In $1$ operation, you choose a switch $i$ that is ON and press it. Then switch $i$ becomes OFF and switch $A_i$ becomes ON. After performing the operation $K$ times, the state became such that only switch $M$ is ON.
In this situation, how many sequences $A$ are possible? Since the answer can be very large, output it modulo $1000000007=10^9+7$.
Input
$N$ $K$ $M$
- $1 \le M \le N \le 10^6$
- $1 \le K \le 10^{18}$
- All inputs are integers.
Output
Print a newline at the end.
Sample
Sample 1
Input
3 1 1
Output
9
If $A_1=1$, the other elements can be anything, so there are $3^2=9$ ways. For example, $A=\{1,2,1\}$ is one such sequence.
Sample 2
Input
1000 1000 1000
Output
10507954
Output the answer modulo $1000000007$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。