{"raw_statement":[{"iden":"problem statement","content":"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.\n\n*   $B_{i,1}=i$.\n*   $B_{i,j+1}=A_{B_{i,j}}\\ (1\\leq j<10^{100})$.\n\nAdditionally, 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$.\nYou 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$."},{"iden":"constraints","content":"*   $1\\leq N \\leq 2\\times 10^5$\n*   $10^8\\leq M \\leq 10^9$\n*   $N$ and $M$ are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$"},{"iden":"sample input 1","content":"4 100000000"},{"iden":"sample output 1","content":"624\n\nAs an example, let us consider the case $A=(2,3,3,4)$.\n\n*   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$.\n*   For $i=2$: we have $B_2=(2,3,3,3,\\dots)$, where one integer, $2$, occurs exactly once, so $S_2=1$.\n*   For $i=3$: we have $B_3=(3,3,3,\\dots)$, where no integers occur exactly once, so $S_3=0$.\n*   For $i=4$: we have $B_4=(4,4,4,\\dots)$, where no integers occur exactly once, so $S_4=0$.\n\nThus, we have $\\displaystyle \\sum_{i=1}^{N} S_i=2+1+0+0=3$.\nIf 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$."},{"iden":"sample input 2","content":"7 1000000000"},{"iden":"sample output 2","content":"5817084"},{"iden":"sample input 3","content":"2023 998244353"},{"iden":"sample output 3","content":"737481389\n\nPrint the sum modulo $M$."},{"iden":"sample input 4","content":"100000 353442899"},{"iden":"sample output 4","content":"271798911"}],"translated_statement":[{"iden":"problem statement","content":"对于一个长度为 $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}})$ 如下。\n\n*   $B_{i,1}=i$.\n*   $B_{i,j+1}=A_{B_{i,j}}\\ (1\\leq j<10^{100})$.\n\n此外，定义 $S_i$ 为在序列 $B_i$ 中恰好出现一次的不同整数的个数。更正式地，$S_i$ 是满足恰好存在一个下标 $j\\ (1\\leq j\\leq 10^{100})$ 使得 $B_{i,j}=k$ 的值 $k$ 的个数。\n给定一个整数 $N$。$A$ 可能的序列共有 $N^N$ 个。求对所有这些序列，$\\displaystyle \\sum_{i=1}^{N} S_i$ 的总和，并对 $M$ 取模。"},{"iden":"constraints","content":"*   $1\\leq N \\leq 2\\times 10^5$\n*   $10^8\\leq M \\leq 10^9$\n*   $N$ 和 $M$ 为整数。"},{"iden":"input","content":"输入从标准输入给出，格式如下：\n\n$N$ $M$"},{"iden":"sample input 1","content":"4 100000000"},{"iden":"sample output 1","content":"624\n\n例如，考虑 $A=(2,3,3,4)$ 的情况。\n\n*   对于 $i=1$：有 $B_1=(1,2,3,3,3,\\dots)$，其中有两个整数 $1$ 和 $2$ 恰好出现一次，因此 $S_1=2$。\n*   对于 $i=2$：有 $B_2=(2,3,3,3,\\dots)$，其中有一个整数 $2$ 恰好出现一次，因此 $S_2=1$。\n*   对于 $i=3$：有 $B_3=(3,3,3,\\dots)$，其中没有整数恰好出现一次，因此 $S_3=0$。\n*   对于 $i=4$：有 $B_4=(4,4,4,\\dots)$，其中没有整数恰好出现一次，因此 $S_4=0$。\n\n因此，$\\displaystyle \\sum_{i=1}^{N} S_i=2+1+0+0=3$。\n如果同样计算其他 $255$ 个序列的 $\\displaystyle \\sum_{i=1}^{N} S_i$，则对全部 $256$ 个序列，这个值的总和为 $624$。"},{"iden":"sample input 2","content":"7 1000000000"},{"iden":"sample output 2","content":"5817084"},{"iden":"sample input 3","content":"2023 998244353"},{"iden":"sample output 3","content":"737481389\n\n输出对 $M$ 取模后的总和。"},{"iden":"sample input 4","content":"100000 353442899"},{"iden":"sample output 4","content":"271798911"}],"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}