题目描述

在 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$ 的余数。

输入格式

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

$N \ P$

输出格式

向标准输出写入一行。输出应包含答案的余数，即描述 $N$ 个活动时间表的序列 $a, b$ 的对数，其中改进的算法产生更多的活动数量，除以 $P$ 的余数。

题目大意

对于以下问题：

给定长度为 $n$ 的序列 $a$、$b$，满足以下条件：

• 在序列 $a$ 与序列 $b$ 中，$1$ 到 $2n$ 的整数各出现恰好一次；
• 对于 $1\le i\le n$，$a_i<b_i$；
• 对于 $1\le i<n$，$a_i<a_{i+1}$。

求：最多能在 $[a_i,b_i]$ 中选出多少个两两不交的区间。

考虑以下算法：

从 $1$ 到 $n$ 枚举 $i$，若 $[a_i,b_i]$ 与所有已经选择的区间都不交，则选择该区间。最后输出选择的区间数。

给定 $n$，求：有多少个满足条件的序列对 $(a,b)$，使得以上算法无法求出正确的结果。答案对 $p$ 取模。

3 100000007

2

4 100000007

28

15 999999937

935834920

提示

【样例解释 #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$，这是 $935834920$ 除以 $999999937$ 的余数。

该样例满足子任务 $3 \sim 6$ 的限制。

【数据范围】

对于所有测试数据，满足 $1 \le N \le 2 \times 10 ^ 4$，$10 ^ 8 < P < 10 ^ 9$，保证 $P$ 是质数，保证所有输入均为整数。

子任务编号	分值	$N \le$
$1$	$5$	$5$
$2$		$8$
$3$	$27$	$30$
$4$	$14$	$300$
$5$	$36$	$3000$
$6$	$13$	$2 \times 10 ^ 4$

题面翻译由 ChatGPT-4o 提供。