# Problem C

Derangement Rotations

A *Derangement* is a permutation $p$ of ${1, 2, \ldots , n}$ where
$p_ i \ne i$ for all
$i$ from $1$ to $n$.

A *rotation* of a sequence $a_1, a_2, \ldots , a_ n$ with offset
$k$ ($1 \le k \le n$) is equal to the
sequence $a_ k$,
$a_{k+1}$, $\ldots $, $a_ n$, $a_1$, $a_2$, $\ldots $, $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, \ldots , n}$ such that $f(D) = n-2$, modulo $p$.

## Input

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

Output a single integer, which is the number of derangements $D$ of size $n$ with $f(D) = n-2$, modulo $p$.

Sample Input 1 | Sample Output 1 |
---|---|

3 1000000007 |
0 |

Sample Input 2 | Sample Output 2 |
---|---|

6 999999937 |
20 |