P9330 [JOIST 2023] 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-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$ 的余数。

**【样例解释 #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 提供。