分数: 600 点
问题陈述
对于长度序列 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 是值的数量 k 这样正好有一个索引 j\ (1\leq j\leq 10^{100}) 满足 B_{i,j}=k.
给你一个整数 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.
如果我们类似地计算 \displaystyle \sum_{i=1}^{N} S_i 为其他 255 序列,该值的总和 256 序列是 624.
示例输入 2
7 1000000000
示例输出 2
5817084
示例输入 3
2023 998244353
示例输出 3
737481389
打印模数之和 M.
示例输入 4
100000 353442899
示例输出 4
271798911