G - Only Once Editorial /

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,22 つで、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