当前没有测试数据。

G - 只出现一次

分数: $600$ 分

题目描述

对于一个长度为 $N$ 的序列 $A = (A_1,A_2,\dots,A_N)$，其中的整数介于 $1$ 和 $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$ 是满足只有一个索引 $j\ (1\leq j\leq 10^{100})$ 使得 $B_{i,j}=k$ 的值 $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$

输出

输出一个整数作为答案。

4 100000000

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$。

7 1000000000

5817084

2023 998244353

737481389

对结果进行 $M$ 取模后输出。

100000 353442899

271798911