#P8340. [AHOI2022] 山河重整

[AHOI2022] 山河重整

题目描述

生活在 998244353998244353 号小宇宙的艾和兰收到了归零者的讯息,决定响应回归运动。他们需要把大部分的物质归还给大宇宙,只留下极少的物质用于在新宇宙重建自己的文明。

艾和兰的文明总共有 nn 个关键信息,编号为 1,2,,n1, 2, \ldots, n。他们需要保留的信息是这些关键信息的一个子集 SS。对于一个编号为 xx 的信息,只要 SS 中一个子集的编号和等于 xx,那么他们设计的漂流瓶就可以在新宇宙将 xx 还原出来。

艾和兰不禁想要思考,他们有多少种选择子集 SS 的方案,使得关键信息 1,2,,n1, 2, \ldots, n 均能被还原?艾和兰自然是只用 11 微秒就算出了方案数的精确数值,现在他们想让你帮忙验算。由于方案数可能很大,你只需要输出方案数对 MM 取模的结果。

输入格式

一行输入两个正整数 N,MN, M

输出格式

输出一行一个整数,表示答案对 MM 取模的结果。

4 1000000007

3

10 1000000007

180

1000 65472

2136

100000 100

96

提示

【样例解释 #1】

总共有以下 33 个集合满足条件:

  • {1,2,3}\{ 1, 2, 3 \}
  • {1,2,4}\{ 1, 2, 4 \}
  • {1,2,3,4}\{ 1, 2, 3, 4 \}

【数据范围】

对于 100%100 \% 的数据,保证 1N5×1051 \le N \le 5 \times {10}^52M1.01×1092 \le M \le 1.01 \times {10}^9

测试点编号 NN \le MM \le
121 \sim 2 2020 1.01×1091.01 \times {10}^9
343 \sim 4 100100
565 \sim 6 50005000
77 3×1053 \times {10}^5 127127
88 5×1055 \times {10}^5
99 3×1053 \times {10}^5 1.01×1091.01 \times {10}^9
1010 5×1055 \times {10}^5