题目描述

对于一个长度为 $N$ 的序列 $A = (A_1,A_2,\\dots,A_N)$，其中的整数取值范围是 $1$ 到 $N$，包括边界值，并给定一个整数 $i\\ (1\\leq i \\leq N)$，我们定义一个长度为 $10^{100}$ 的序列 $B_i=(B_{i,1},B_{i,2},\\dots,B_{i,10^{100}})$，如下所示：

• $B_{i,1}=i$。
• $B_{i,j+1}=A_{B_{i,j}}\\ (1\\leq j<10^{100})$。

另外，我们定义 $S_i$ 是序列 $B_i$ 中仅出现一次的整数的个数。更准确地说，$S_i$ 是满足 $B_{i,j}=k$ 的唯一索引 $j\\ (1\\leq j\\leq 10^{100})$ 的个数。

给定一个整数 $N$。存在 $N^N$ 种可能的 $A$ 序列。求所有这些序列中 $\\displaystyle \\sum_{i=1}^{N} S_i$ 的和，对 $M$ 取模。

约束条件

• $1\\leq N \\leq 2\\times 10^5$
• $10^8\\leq M \\leq 10^9$
• $N$ 和 $M$ 是整数。

输入

输入以以下格式从标准输入给出：

$N$ $M$

输出

以整数形式输出答案。

示例输入1

4 100000000

示例输出1

624

举个例子，假设 $A=(2,3,3,4)$。

• 当 $i=1$ 时，我们有 $B_1=(1,2,3,3,3,\\dots)$，其中的两个整数 $1$ 和 $2$ 出现一次，所以 $S_1=2$。
• 当 $i=2$ 时，我们有 $B_2=(2,3,3,3,\\dots)$，其中的一个整数 $2$ 出现一次，所以 $S_2=1$。
• 当 $i=3$ 时，我们有 $B_3=(3,3,3,\\dots)$，其中没有整数出现一次，所以 $S_3=0$。
• 当 $i=4$ 时，我们有 $B_4=(4,4,4,\\dots)$，其中没有整数出现一次，所以 $S_4=0$。

因此，我们有 $\\displaystyle \\sum_{i=1}^{N} S_i=2+1+0+0=3$。

如果我们类似地计算其他 $255$ 种情况下的 $\\displaystyle \\sum_{i=1}^{N} S_i$，则所有 $256$ 种情况的这个值的总和为 $624$。

示例输入2

7 1000000000

示例输出2

5817084

示例输入3

2023 998244353

示例输出3

737481389

按照 $M$ 取模后输出答案。

示例输入4

100000 353442899

示例输出4

271798911