题目描述

In JOI Kingdom, a national festival is held once a year. During the period of the festival, there are $N$ events in total. The schedule for each event is already fixed. The schedule of the $N$ events are described by sequences $a, b$ of length $N$ satisfying the following conditions.

• Every integer between $1$ and $2N$, inclusive, appears as an element of $a$ or $b$.
• $a_i < b_i \ (1 \le i \le N)$.
• $a_i < a_{i + 1} \ (1 \le i \le N - 1)$.

The $i$-th event will start at $a_i$ minutes after the beginning of the festival, and end at $b_i$ minutes after the beginning of the festival.

Participants of the festival may choose any events in which they will participate. However, it is not allowed to participate in two events whose schedules overlap. (Note that the starting times and the ending times of the events are different from each other.)

JOI-kun wants to participate in as many events as possible. Until last year, he chose the events in which he participated by the following procedures on a computer.

For $i = 1, 2, \dots, N$，the following are done in this order.

If the schedule of the $i$-th event does not overlap the schedules of the other events in which he already chose to participate, he will participate in the $i$-th event. Otherwise, he will not participate in the $i$-th event.

However, after studying computer science, JOI-kun noticed that the above algorithm does not necessarily maximize the number of events in which JOI-kun will participate. From this year, JOI-kun will use an improved algorithm. Using the improved algorithm, JOI-kun will be able to maximize the number of events in which JOI-kun will participate.

JOI-kun wants to know the number of cases where the improved algorithm produces a larger number of events.

Write a program which, given the integer $N$ and a large prime number $P$, calculates the number of pairs of sequences $a, b$ describing the schedules of the $N$ events for which the improved algorithm produces a larger number of events. Since the answer can be very large, your program should output the remainder of the answer when divided by $P$.

输入格式

Read the following data from the standard input.

$N \ P$

输出格式

Write one line to the standard output. The output should contain the remainder of the answer, the number of pairs of sequences $a, b$ describing the schedules of the $N$ events for which the improved algorithm produces a larger number of events, when divided by $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】

For example, consider the case where $a = (1, 2, 4)$ and $b = (6, 3, 5)$. If JOI-kun uses the algorithm used until last year, he will participate in the first event only. On the other hand, if he uses a correct algorithm to maximize the number of events, he will participate in the second event and the third event. Thus, he will participate in two events. In this case, the improved algorithm produces a larger number of events.

The following are the pair of sequences $a, b$ for which the improved algorithm produces a larger number of events.

• $a = (1, 2, 4), b = (6, 3, 5)$
• $a = (1, 2, 4), b = (5, 3, 6)$

Therefore, output $2$, which is the remainder of $2$ when divided by $100000007$.

该样例满足所有子任务的限制。

【样例解释 #2】

There are $28$ pairs of sequences $a, b$ satisfying the condition. Therefore, output $28$, which is the remainder of $28$ when divided by $100000007$.

该样例满足所有子任务的限制。

【样例解释 #3】

There are $5295044602247148$ pairs of sequences $a, b$ satisfying the condition. Therefore, output $935834920$, which is the remainder of $935834920$ when divided by $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$