在 JOI 王国，每年举办一次全国性的节日。节日期间共有 $N$ 个活动。每个活动的日程安排都是固定的。这 $N$ 个活动的日程由长度为 $N$ 的序列 $a$ 和 $b$ 描述，满足以下条件：

• $1$ 到 $2N$ 之间的每个整数（包含 $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-kun 希望尽可能多地参加活动。直到去年，他通过计算机上的以下程序来选择参加的活动：

对于 $i = 1, 2, \dots, N$，按此顺序执行以下操作： 如果第 $i$ 个活动的日程与他已经选择参加的其他活动的日程不重叠，他将参加第 $i$ 个活动。否则，他不参加第 $i$ 个活动。

然而，在学习了计算机科学之后，JOI-kun 注意到上述算法并不一定能使他参加的活动数量最大化。从今年开始，JOI-kun 将使用一种改进的算法。使用改进的算法，JOI-kun 将能够使他参加的活动数量最大化。

JOI-kun 想知道改进算法产生的活动数量比原算法更多的情形有多少种。

编写一个程序，给定整数 $N$ 和一个大素数 $P$，计算有多少对描述 $N$ 个活动日程的序列 $a, b$，使得改进算法产生的活动数量更多。由于答案可能非常大，请输出答案除以 $P$ 的余数。

输入格式

从标准输入读取以下数据：

$N \ P$

输出格式

输出一行到标准输出。输出应包含改进算法产生的活动数量更多的序列对 $a, b$ 的数量除以 $P$ 的余数。

数据范围

• $1 \le N \le 20\,000$
• $10^8 < P < 10^9$
• $P$ 是一个素数。
• 给定的值均为整数。

子任务

1. (5 分) $N \le 5$
2. (5 分) $N \le 8$
3. (27 分) $N \le 30$
4. (14 分) $N \le 300$
5. (36 分) $N \le 3\,000$
6. (13 分) 无附加限制。

样例

样例输入 1

3 100000007

样例输出 1

2

说明 1

例如，考虑 $a = (1, 2, 4)$ 且 $b = (6, 3, 5)$ 的情况。如果 JOI-kun 使用去年之前的算法，他将只参加第一个活动。另一方面，如果他使用正确的算法来最大化活动数量，他将参加第二个活动和第三个活动。因此，他将参加两个活动。在这种情况下，改进算法产生的活动数量更多。

以下是改进算法产生更多活动数量的序列对 $a, b$： $a = (1, 2, 4), b = (6, 3, 5)$ $a = (1, 2, 4), b = (5, 3, 6)$

因此，输出 2，即 2 除以 100 000 007 的余数。 该样例输入满足所有子任务的限制。

样例输入 2

4 100000007

样例输出 2

28

说明 2

共有 28 对满足条件的序列 $a, b$。因此，输出 28，即 28 除以 100 000 007 的余数。 该样例输入满足所有子任务的限制。

样例输入 3

15 999999937

样例输出 3

935834920

说明 3

共有 5 295 044 602 247 148 对满足条件的序列 $a, b$。因此，输出 935 834 920，即 5 295 044 602 247 148 除以 999 999 937 的余数。 该样例输入满足子任务 3, 4, 5, 6 的限制。