English Problem Statement

伏特正在设计马拉松赛场的道路，以确保物资运输和观众流动的秩序。

伏特选定了 $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$ 是素数。

时间限制：$\mathtt{\text{1s}}$

空间限制：$\mathtt{\text{512MB}}$