← 返回题目列表

AtCoder · abc284_g

G. 只有一次

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

对于长度序列 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 是值的数量 k 这样正好有一个索引 j\ (1\leq j\leq 10^{100}) 满足 B_{i,j}=k.

给你一个整数 N。有 N^N 序列可以是 A。求总和 \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 和 2,只发生一次,所以 S_1=2.
  • 对于 i=2:我们有 B_2=(2,3,3,3,\dots),其中一个整数, 2,只发生一次,所以 S_2=1.
  • 对于 i=3:我们有 B_3=(3,3,3,\dots),其中没有整数恰好出现一次,所以 S_3=0.
  • 对于 i=4:我们有 B_4=(4,4,4,\dots),其中没有整数恰好出现一次,所以 S_4=0.

因此,我们有 \displaystyle \sum_{i=1}^{N} S_i=2+1+0+0=3.

如果我们类似地计算 \displaystyle \sum_{i=1}^{N} S_i 为其他 255 序列,该值的总和 256 序列是 624.


示例输入 2

7 1000000000

示例输出 2

5817084

示例输入 3

2023 998244353

示例输出 3

737481389

打印模数之和 M.


示例输入 4

100000 353442899

示例输出 4

271798911