题目描述

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

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

• 从 $1$ 到 $2N$ 的整数（包含两端）在序列 $a,b$ 中出现且只出现一次
• $a_i<b_i\ (1\le i\le N)$
• $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$ 取模后的值即可。

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$ 模 $100\ 000\ 007$ 为 $2$，因此输出 $2$。

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

4 100000007

28

有 $28$ 对序列 $a,b$​ 满足条件，由于 $28$ 模 $100\ 000\ 007$ 为 $28$，因此输出 $28$。

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

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$ 是一个质数

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