No.1978 Permutation Repetition
Problem Statement
You are given positive integers $N,M$ and a permutation $A=(A_1,A_2,...,A_N)$.
How many permutations $P=(P_1,P_2,...,P_N)$ satisfy the following condition? Find the count modulo $10^9+7$.
Constraints
- $\displaystyle 1 \leq N \leq 10^3$
- $\displaystyle 1 \leq M \leq 10^9$
- $\displaystyle 1 \leq A_i \leq N$
- $\displaystyle A_i \neq A_j \ (i \neq j)$
- All inputs are integers.
Input
The input is given from standard input in the following format.
$N\ \ M$ $A_1\ \ A_2\ \dots \ A_N$
Output
Output the computed value, followed by a newline.
Sample
Sample 1
Input
4 2 1 2 3 4
Output
10
$P=(1,4,3,2),(4,3,2,1)$ and others satisfy the condition.
For example, when $P=(1,4,3,2)$, $x$ changes as follows:
- when $i=1$, $1 \to 1 \to 1$
- when $i=2$, $2 \to 4 \to 2$
- when $i=3$, $3 \to 3 \to 3$
- when $i=4$, $4 \to 2 \to 4$
In each case, the final value of $x$ equals $A_i$.
Sample 2
Input
4 2 4 3 1 2
Output
0
No permutation $P$ satisfies the condition.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
magsta
shino16