题目描述

题目译自 JOISC 2023 Day1 T2 「JOI 国のお祭り事情 2 / Festivals in JOI Kingdom 2」

在 JOI 国，每年会举行一次全国性的节日庆典。在节日期间，共会进行 $N$ 场活动。每场活动的时间计划表已经确定，这 $N$ 个活动的计划表用长为 $N$ 的序列 $a,b$ 表示，序列满足以下条件：

1. 从 $1$ 到 $2N$ 的整数（包含两端）在序列 $a,b$ 中出现且只出现一次
2. $a_i < b_i$ $(1 \le i \le N)$
3. $a_i < a_{i+1}$ $(1 \le i \le N-1)$

第 $i$ 个活动会在节日开始之后的 $a_i$ 分钟时开始，在节日开始之后的 $b_i$ 分钟结束。

节日庆典的参与者可以参加任意活动。然而，参与者不允许参加两个时间重叠的活动。注意活动开始和结束之间两两不同。

JOI 君想要参加尽可能多的活动。直到去年，他都使用如下程序来选择他将参与的活动：

对于 $i=1,2,\ldots,N$，按此顺序进行如下操作。
如果第 $i$ 个活动的时间不与他已经决定参加的活动时间重叠，那么他就会参加第 $i$ 个活动。否则他不会参加第 $i$ 个活动。

然而，在学习计算机科学后，JOI 君注意到上述算法不一定最大化 JOI 君参加的活动数。从今年开始，JOI 君会使用一个改进的算法，使用这个改进的算法，JOI 君可以最大化他所参加的活动数。

JOI 君想知道改进的算法在多少种情况下会输出更大的参加活动数。

给定 $N$ 和一个大质数 $P$，写一个程序计算有多少对描述时间安排且长为 $N$ 的序列 $a,b$，满足改进的算法会输出更大的参加活动数。因为答案可能很大，你的程序只需输出这个值对 $P$ 取模后的值即可。

---

输入格式

第一行输入两个整数 $N, P$。

输出格式

输出一行一个整数表示答案，因为答案可能很大，你的程序只需输出这个值对 $P$ 取模后的值即可。

---

样例

样例 1

输入

3 100000007

输出

2

例如，考虑当 $a=(1,2,4), b=(6,3,5)$ 的情况。如果 JOI 君使用直到去年都在用的算法，他只会参加第一个活动。如果他用了正确的最大化活动参加数的算法，他会参加第二和第三个活动。因此，他将参加两个活动。这种情况下，改进的算法将输出更大的活动参加数。

下面是改进算法将输出更大的活动参加数的序列 $a,b$：

• $a=(1,2,4), b=(6,3,5)$
• $a=(1,2,4), b=(5,3,6)$

由于 $2$ 模 $100000007$ 为 $2$，因此输出 $2$。

这组样例满足所有子任务的限制。

---

样例 2

输入

4 100000007

输出

28

有 $28$ 对序列 $a,b$ 满足条件，由于 $28$ 模 $100000007$ 为 $28$，因此输出 $28$。

这组样例满足所有子任务的限制。

---

样例 3

输入

15 999999937

输出

935834920

有 $5\ 295\ 044\ 602\ 247\ 148$ 对序列 $a,b$ 满足条件，由于 $5\ 295\ 044\ 602\ 247\ 148$ 模 $999\ 999\ 937$ 为 $935\ 834\ 920$，因此输出 $935\ 834\ 920$。

这组样例满足子任务 $3,4,5,6$ 的限制。

---

数据范围与提示

对于所有输入数据，满足：

• $1 \le N \le 20\ 000$
• $10^8 < P < 10^9$
• $P$ 是一个质数

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分值
1	$N \le 5$	5
2	$N \le 8$
3	$N \le 30$	27
4	$N \le 300$	14
5	$N \le 3\ 000$	36
6	无附加限制	13