{"raw_statement":[{"iden":"statement","content":"在 JOI 王国，每年都会举行一次全国性的节日。在节日期间，总共有 $N$ 个活动。每个活动的时间表已经固定。$N$ 个活动的时间表由长度为 $N$ 的序列 $a, b$ 描述，满足以下条件：\n\n- 从 $1$ 到 $2N$ 之间的每个整数都出现在 $a$ 或 $b$ 中。\n- $a_i < b_i \\ (1 \\le i \\le N)$。\n- $a_i < a_{i + 1} \\ (1 \\le i \\le N - 1)$。\n\n第 $i$ 个活动将在节日开始后的 $a_i$ 分钟开始，并在节日开始后的 $b_i$ 分钟结束。\n\n节日的参与者可以选择参加任意活动。然而，不允许参加时间表重叠的两个活动。（注意，活动的开始时间和结束时间彼此不同。）\n\nJOI-kun 想参加尽可能多的活动。直到去年，他通过计算机使用以下程序选择参加的活动：\n\n> 对于 $i = 1, 2, \\dots, N$，按以下顺序进行。\n> > 如果第 $i$ 个活动的时间表与他已经选择参加的其他活动的时间表不重叠，他将参加第 $i$ 个活动。否则，他将不参加第 $i$ 个活动。\n\n然而，在学习了计算机科学之后，JOI-kun 注意到上述算法并不一定能最大化他参加的活动数量。从今年开始，JOI-kun 将使用改进的算法。使用改进的算法，JOI-kun 将能够最大化他参加的活动数量。\n\nJOI-kun 想知道使用改进算法时，产生更多活动数量的情况数。\n\n编写一个程序，给定整数 $N$ 和一个大质数 $P$，计算出描述 $N$ 个活动时间表的序列 $a, b$ 的对数，其中改进的算法产生更多的活动数量。由于答案可能非常大，程序应输出答案除以 $P$ 的余数。"},{"iden":"input","content":"从标准输入读取以下数据。\n\n> $N \\ P$"},{"iden":"output","content":"向标准输出写入一行。输出应包含答案的余数，即描述 $N$ 个活动时间表的序列 $a, b$ 的对数，其中改进的算法产生更多的活动数量，除以 $P$ 的余数。"},{"iden":"note","content":"**【样例解释 #1】**\n\n例如，考虑 $a = (1, 2, 4)$ 和 $b = (6, 3, 5)$ 的情况。如果 JOI-kun 使用去年使用的算法，他将只参加第一个活动。另一方面，如果他使用正确的算法来最大化活动数量，他将参加第二个和第三个活动。因此，他将参加两个活动。在这种情况下，改进的算法产生了更多的活动数量。\n\n以下是改进的算法产生更多活动数量的序列对 $a, b$：\n\n- $a = (1, 2, 4), b = (6, 3, 5)$\n- $a = (1, 2, 4), b = (5, 3, 6)$\n\n因此，输出 $2$，这是 $2$ 除以 $100000007$ 的余数。\n\n该样例满足所有子任务的限制。\n\n**【样例解释 #2】**\n\n有 $28$ 对序列 $a, b$ 满足条件。因此，输出 $28$，这是 $28$ 除以 $100000007$ 的余数。\n\n该样例满足所有子任务的限制。\n\n**【样例解释 #3】**\n\n有 $5295044602247148$ 对序列 $a, b$ 满足条件。因此，输出 $935834920$，这是 $5295044602247148$ 除以 $999999937$ 的余数。\n\n该样例满足子任务 $3 \\sim 6$ 的限制。\n\n**【数据范围】**\n\n对于所有测试数据，满足 $1 \\le N \\le 2 \\times 10 ^ 4$，$10 ^ 8 < P < 10 ^ 9$，保证 $P$ 是质数，保证所有输入均为整数。\n\n|子任务编号|分值|$N \\le$|\n|:-:|:-:|:-:|\n|$1$|$5$|$5$|\n|$2$|$5$|$8$|\n|$3$|$27$|$30$|\n|$4$|$14$|$300$|\n|$5$|$36$|$3000$|\n|$6$|$13$|$2 \\times 10 ^ 4$|\n\n题面翻译由 ChatGPT-4o 提供。"}],"translated_statement":null,"sample_group":[["3 100000007\n","2\n"],["4 100000007\n","28\n"],["15 999999937\n","935834920\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}