Score : $600$ points

问题描述

对于一个长度为 $N$ 的序列 $A = (A_1, A_2, \dots, A_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$ 取模。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 11:54:34