JOI Kingdom Festival Events

In JOI Kingdom a national festival is held once a year. During the festival there are \(N\) events. The schedule of the events is described by two sequences of length \(N\), namely \(a=(a_1,a_2,\dots,a_N)\) and \(b=(b_1,b_2,\dots,b_N)\) which satisfy the following conditions:

• Every integer between 1 and \(2N\) appears exactly once as an element of either \(a\) or \(b\).
• For every \(1 \le i \le N\), \(a_i < b_i\) holds.
• \(a_1 < a_2 < \cdots < a_N\) holds.

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. A participant may choose any subset of events to attend, with the restriction that no two chosen events have overlapping time intervals (note that starting times and ending times are all distinct).

Until last year, JOI‐kun used the following algorithm when choosing his events:

For \(i=1,2,\dots,N\) in order, if the \(i\)-th event does not overlap with any event already chosen then select it; otherwise, do not select it.

However, JOI‐kun realized that this simple procedure does not always yield the maximum possible number of events he could attend. He has now devised an improved algorithm which does achieve the maximum (that is, the solution to the standard interval scheduling problem).

JOI‐kun is curious: for how many pairs of sequences \(a\) and \(b\) (that is, for how many possible schedules) does the improved algorithm yield a strictly larger number of events than the old algorithm? Since the answer may be very large, output it modulo the given prime \(P\).

Input example: For example, if \(N=2\) it turns out that no schedule makes a difference between the two algorithms, whereas for larger \(N\) differences may occur.

Note on algorithms: The optimal (improved) algorithm is equivalent to the greedy algorithm that selects intervals in order of increasing finishing times. In contrast the old algorithm processes events in order of increasing starting times. Due to the structure of the schedules, these two methods sometimes choose the same set of events, but in other cases the improved algorithm is able to choose strictly more events.

Your task is to compute the number of schedules (pairs of sequences \(a\) and \(b\) satisfying the above conditions) for which the improved algorithm yields more events than the old algorithm. The answer should be given modulo \(P\).

inputFormat

The input consists of a single line containing two integers \(N\) and \(P\), where \(N\) is the number of events and \(P\) is a large prime number. \(N\) will satisfy \(1 \le N \le 10^5\) (or an appropriate bound) and \(P\) is given so that your answer modulo \(P\) fits in standard 64-bit integer type.

outputFormat

Output a single integer, the number of pairs of sequences \(a\) and \(b\) for which the improved algorithm produces a larger number of events than the old algorithm, taken modulo \(P\).

sample

2 1000003

0