伏特正在设计马拉松赛场的道路,以确保物资运输和观众流动的秩序。
伏特选定了 $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}$