题目描述

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

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

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

输入格式

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

输出格式

输出一行一个整数，表示答案对 $M$ 取模的结果。

样例 #1

样例输入 #1

4 1000000007

样例输出 #1

3

样例 #2

样例输入 #2

10 1000000007

样例输出 #2

180

样例 #3

样例输入 #3

1000 65472

样例输出 #3

2136

样例 #4

样例输入 #4

100000 100

样例输出 #4

96

提示

【样例解释 #1】

总共有以下 $3$ 个集合满足条件：

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

【数据范围】

对于 $100 \%$ 的数据，保证 $1 \le N \le 5 \times {10}^5$，$2 \le M \le 1.01 \times {10}^9$。

测试点编号	$N \le$	$M \le$
$1 \sim 2$	$20$	$1.01 \times {10}^9$
$3 \sim 4$	$100$
$5 \sim 6$	$5000$
$7$	$3 \times {10}^5$	$127$
$8$	$5 \times {10}^5$
$9$	$3 \times {10}^5$	$1.01 \times {10}^9$
$10$	$5 \times {10}^5$