시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 63 | 23 | 20 | 36.364% |
A Derangement is a permutation $p$ of $1, 2, \dots , n$ where $p_i \ne i$ for all $i$ from $1$ to $n$.
A rotation of a sequence $a_1, a_2, \dots , a_n$ with offset $k$ ($1 \le k \le n$) is equal to the sequence $a_k, a_{k+1}, \dots, a_n, a_1, a_2, \dots, a_{k-1}$. A sequence of length $n$ has at most $n$ distinct rotations.
Given a derangement $D$, let $f(D)$ denote the number of distinct rotations of $D$ that are also derangements. For example, $f([2, 1]) = 1$, $f([3, 1, 2]) = 2$.
Given $n$ and a prime number $p$, count the number of derangements $D$ of $1, 2, \dots , n$ such that $f(D) = n - 2$, modulo $p$.
The single line of input contains two integers $n$ ($3 \le n \le 10^6$) and $p$ ($10^8 \le p \le 10^9 + 7$), where $n$ is a permutation size, and $p$ is a prime number.
Output a single integer, which is the number of derangements $D$ of size $n$ with $f(D) = n - 2$, modulo $p$.
3 1000000007
0
6 999999937
20