Festivals in JOI Kingdom 2

Time limit6sMemory limit1024 MB

Summary

Count the pairs of sequences a and b of N intervals using each value from 1 to 2N once, where greedy selection by start time is not optimal, modulo prime P.

Level: Hard9 of 10
Topics: Dynamic programming, Combinatorics, Greedy
Solved: No attempts yet

Problem

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

Every integer from $1$ to $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 starts at $a_i$ minutes after the beginning of the festival and ends at $b_i$ minutes after the beginning of the festival.

Participants may choose any events they like. However, they may not take part in two events whose schedules overlap. (The starting times and ending times of all events are different from each other.)

JOI-kun wants to take part in as many events as possible. Until last year, he chose events on a computer with the following procedure.

For $i = 1, 2, \dots, N$ $i = 1, 2, \dots, N$ , do the following in this order.
- If the schedule of the $i$ -th event does not overlap the schedules of the events he has already chosen, he takes part in the $i$ -th event. Otherwise, he does not.

After studying computer science, JOI-kun noticed that this procedure does not always maximize the number of events he takes part in. Starting this year, he will use an improved algorithm. With the improved algorithm, JOI-kun will be able to maximize the number of events he takes part in.

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

Given the integer $N$ and a large prime $P$ , write a program that counts the pairs of sequences $a$ and $b$ describing the schedules for which the improved algorithm produces a larger number of events. Output the count modulo $P$ .

Input

Read the following data from standard input.

$N$ $P$

Output

Write one line to standard output. The line contains the number of pairs of sequences $a$ and $b$ describing the schedules of the $N$ events for which the improved algorithm produces a larger number of events, modulo $P$ .

Constraints

$1 \le N \le 20\,000$ .
$10^8 < P < 10^9$ .
$P$ is a prime number.
All given values are integers.

Examples3

Example 1
Input
```
3 100000007
```
Expected output
```
2
```
Example 2
Input
```
4 100000007
```
Expected output
```
28
```
Example 3
Input
```
15 999999937
```
Expected output
```
935834920
```