题目描述

$1$ 以上 $N$ 以下の整数からなる長さ $N$ の数列 $A\ =\ (A_1,A_2,\dots,A_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$ のなかでちょうど $1$ 度だけ出てくる数の種類数」と定義します。 より厳密には、$S_i$ は「$B_{i,j}=k$ を満たす $j\ (1\leq\ j\leq\ 10^{100})$ がちょうど $1$ つであるような $k$ の数」です。

整数 $N$ が与えられます。数列 $A$ として考えられるものは $N^N$ 通りありますが、それら全てに対して $\displaystyle\ \sum_{i=1}^{N}\ S_i$ を求め、 その総和を $M$ で割った余りを答えてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$

输出格式

答えを整数として出力せよ。

题目大意

给定 $n$，对于一个长度为 $n$，值域为 $n$ 的序列 $A$，按如下方法构造无限序列 $B_i(1 \le i \le n)$：

• $B_{i,1} = i$
• $B_{i,j} = A_{B_{i,j-1}}(j > 1)$

记 $S_i$ 为 $B_i$ 中只出现了一次的元素的个数，定义序列 $A$ 的价值为 $\sum_{i=1}^n S_i$，现在请求出所有 $n^n$ 个可能的序列 $A$ 的价值之和对 $M$ 取模的结果。

$n \le 2 \times 10^5, 10^8 \le M \le 10^9$.

4 100000000

624

7 1000000000

5817084

2023 998244353

737481389

100000 353442899

271798911

提示

制約

• $1\leq\ N\ \leq\ 2\times\ 10^5$
• $10^8\leq\ M\ \leq\ 10^9$
• $N,M$ は整数

Sample Explanation 1

例として、$A=(2,3,3,4)$ の場合を考えます。 - $i=1$ のとき : $B_1=(1,2,3,3,3,\dots)$ となるから、$1$ 度だけ出てくる数は $1,2$ の $2$ つで、$S_1=2$ - $i=2$ のとき : $B_2=(2,3,3,3,\dots)$ となるから、$1$ 度だけ出てくる数は $2$ のみで、$S_2=1$ - $i=3$ のとき : $B_3=(3,3,3,\dots)$ となるから、$1$ 度だけ出てくる数は存在せず、$S_3=0$ - $i=4$ のとき : $B_4=(4,4,4,\dots)$ となるから、$1$ 度だけ出てくる数は存在せず、$S_4=0$ よって、$\displaystyle\ \sum_{i=1}^{N}\ S_i=2+1+0+0=3$ です。 他の $255$ 通りの $A$ に対しても同様に $\displaystyle\ \sum_{i=1}^{N}\ S_i$ を計算したうえで、 $256$ 通り全ての総和をとると $624$ になります。

Sample Explanation 3

総和を $M$ で割った余りを出力してください。