只出现一次

题目描述

对于长度为 $N$、由 $1$ 到 $N$(含)之间的整数组成的序列 $A = (A_1,A_2,\dots,A_N)$,以及整数 $i\ (1 \le i \le 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 \le j \lt 10^{100})$。

另外,定义 $S_i$ 为序列 $B_i$ 中恰好出现一次的不同整数的个数。更形式化地说,$S_i$ 是满足「恰好存在一个下标 $j\ (1 \le j \le 10^{100})$ 使得 $B_{i,j}=k$」的 $k$ 的个数。

给定一个整数 $N$。可以成为 $A$ 的序列共有 $N^N$ 种。求所有序列的 $\displaystyle \sum_{i=1}^{N} S_i$ 之和,对 $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

数据范围

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