/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
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 で割った余りを答えてください。
制約
- 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 度だけ出てくる数は 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 になります。
入力例 2
7 1000000000
出力例 2
5817084
入力例 3
2023 998244353
出力例 3
737481389
総和を M で割った余りを出力してください。
入力例 4
100000 353442899
出力例 4
271798911
Score : 600 points
Problem Statement
For a sequence of length N, A = (A_1,A_2,\dots,A_N), consisting of integers between 1 and N, inclusive, and an integer i\ (1\leq i \leq N), let us define a sequence of length 10^{100}, B_i=(B_{i,1},B_{i,2},\dots,B_{i,10^{100}}), as follows.
- B_{i,1}=i.
- B_{i,j+1}=A_{B_{i,j}}\ (1\leq j<10^{100}).
Additionally, let us define S_i as the number of distinct integers that occur exactly once in the sequence B_i. More formally, S_i is the number of values k such that exactly one index j\ (1\leq j\leq 10^{100}) satisfies B_{i,j}=k.
You are given an integer N. There are N^N sequences that can be A. Find the sum of \displaystyle \sum_{i=1}^{N} S_i over all of them, modulo M.
Constraints
- 1\leq N \leq 2\times 10^5
- 10^8\leq M \leq 10^9
- N and M are integers.
Input
The input is given from Standard Input in the following format:
N M
Output
Print the answer as an integer.
Sample Input 1
4 100000000
Sample Output 1
624
As an example, let us consider the case A=(2,3,3,4).
- For i=1: we have B_1=(1,2,3,3,3,\dots), where two integers, 1 and 2, occur exactly once, so S_1=2.
- For i=2: we have B_2=(2,3,3,3,\dots), where one integer, 2, occurs exactly once, so S_2=1.
- For i=3: we have B_3=(3,3,3,\dots), where no integers occur exactly once, so S_3=0.
- For i=4: we have B_4=(4,4,4,\dots), where no integers occur exactly once, so S_4=0.
Thus, we have \displaystyle \sum_{i=1}^{N} S_i=2+1+0+0=3.
If we similarly compute \displaystyle \sum_{i=1}^{N} S_i for the other 255 sequences, the sum of this value over all 256 sequences is 624.
Sample Input 2
7 1000000000
Sample Output 2
5817084
Sample Input 3
2023 998244353
Sample Output 3
737481389
Print the sum modulo M.
Sample Input 4
100000 353442899
Sample Output 4
271798911