题目描述

题目译自 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

4 100000007

28

15 999999937

935834920

数据范围与提示

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

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

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