伏特正在设计马拉松赛场的道路，以确保物资运输和观众流动的秩序。
伏特选定了 $n$ 个站点，他可以在 $n$ 个站点之间铺设若干单向道路，不能铺设重复的道路。
伏特不希望跳蚤们迷路：铺设的道路不能有环。
伏特希望赛场道路有良好的交通：不能存在三个站点 $(a,b,c)$，使得 $a$ 不能到达 $b$，$b$ 不能到达 $c$，$c$ 不能到达 $a$。
称满足上述两条限制的道路铺设方案为好图。伏特想知道好图有多少种，这个数字可能很大，你需要求出答案在模素数 $P$ 意义下的值。
输入格式
一行两个整数，分别表示 $n$ 和 $P$。
输出格式
一行一个整数，表示答案对 $P$ 取模的值。
样例一
input
3 835199921
output
18
explanation
下记 $(x,y)$ 表示 $x$ 到 $y$ 的单向道路。
选择边集 $(1,2),(1,3)$ 是好图，通过交换点的标号可以获得 3 种好图。
选择边集 $(1,2),(2,3)$ 是好图，通过交换点的标号可以获得 6 种好图。
选择边集 $(1,2),(1,3),(2,3)$ 是好图，通过交换点的标号可以获得 6 种好图。
选择边集 $(1,3),(2,3)$ 是好图，通过交换点的标号可以获得 3 种好图。
选择边集 $(1,2)$ 不是好图，因为存在：$1$ 无法到 $3$，$3$ 无法到 $2$，$2$ 无法到 $1$。
选择边集 $(1,2),(2,1)$ 不是好图，因为存在环 $(1,2),(2,1)$，不属于 DAG。
一共有 $3+6+6+3=18$ 种三个点的好图。
样例二
input
16 828234769
output
372590002
样例三~九
见附件下载。
对于所有样例，保证第 $i$ 个样例满足第 $i$ 个子任务的约束。
数据范围
对于所有数据，保证 $1\le n\le 10^6$，$10^8\le P\le 10^9$，$P$ 是素数。
| 子任务编号 | 分值 | $n\le$ | 特殊性质 |
|---|---|---|---|
| $1$ | $12$ | $5$ | 无 |
| $2$ | $12$ | $18$ | 无 |
| $3$ | $8$ | $200$ | 无 |
| $4$ | $10$ | $5000$ | $P=998244353$ |
| $5$ | $10$ | $5000$ | 无 |
| $6$ | $12$ | $2\times 10^5$ | $P=998244353$ |
| $7$ | $12$ | $2\times 10^5$ | 无 |
| $8$ | $12$ | $10^6$ | $P=998244353$ |
| $9$ | $12$ | $10^6$ | 无 |
时间限制：$\texttt{1s}$
空间限制：$\texttt{512MB}$
鄂公网安备 42010202000505 号