在 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-kun 想参加尽可能多的活动。直到去年，他通过计算机使用以下程序选择参加的活动：
> 对于 $i = 1, 2, \dots, N$，按以下顺序进行。
> > 如果第 $i$ 个活动的时间表与他已经选择参加的其他活动的时间表不重叠，他将参加第 $i$ 个活动。否则，他将不参加第 $i$ 个活动。
然而，在学习了计算机科学之后，JOI-kun 注意到上述算法并不一定能最大化他参加的活动数量。从今年开始，JOI-kun 将使用改进的算法。使用改进的算法，JOI-kun 将能够最大化他参加的活动数量。
JOI-kun 想知道使用改进算法时，产生更多活动数量的情况数。
编写一个程序，给定整数 $N$ 和一个大质数 $P$，计算出描述 $N$ 个活动时间表的序列 $a, b$ 的对数，其中改进的算法产生更多的活动数量。由于答案可能非常大，程序应输出答案除以 $P$ 的余数。
## Input
从标准输入读取以下数据。
> $N \ P$
## Output
向标准输出写入一行。输出应包含答案的余数，即描述 $N$ 个活动时间表的序列 $a, b$ 的对数，其中改进的算法产生更多的活动数量，除以 $P$ 的余数。
[samples]
## Note
**【样例解释 #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$ 除以 $100000007$ 的余数。
该样例满足所有子任务的限制。
**【样例解释 #2】**
有 $28$ 对序列 $a, b$ 满足条件。因此，输出 $28$，这是 $28$ 除以 $100000007$ 的余数。
该样例满足所有子任务的限制。
**【样例解释 #3】**
有 $5295044602247148$ 对序列 $a, b$ 满足条件。因此，输出 $935834920$，这是 $5295044602247148$ 除以 $999999937$ 的余数。
该样例满足子任务 $3 \sim 6$ 的限制。
**【数据范围】**
对于所有测试数据，满足 $1 \le N \le 2 \times 10 ^ 4$，$10 ^ 8 < P < 10 ^ 9$，保证 $P$ 是质数，保证所有输入均为整数。
|子任务编号|分值|$N \le$|
|:-:|:-:|:-:|
|$1$|$5$|$5$|
|$2$|$5$|$8$|
|$3$|$27$|$30$|
|$4$|$14$|$300$|
|$5$|$36$|$3000$|
|$6$|$13$|$2 \times 10 ^ 4$|
题面翻译由 ChatGPT-4o 提供。