Counting Interesting Permutations

Given a positive integer \(n\), we define a sequence of length \(2n\) as interesting if and only if it satisfies the following conditions:

• The sequence is a permutation of the set \(\{1,2,\dots,2n\}\).
• If the sequence is \(\{a_1, a_2, \dots, a_{2n}\}\), then the subsequence of all odd-indexed terms \(a_1,a_3,\dots,a_{2n-1}\) is in strictly increasing order and the subsequence of all even-indexed terms \(a_2,a_4,\dots,a_{2n}\) is in strictly increasing order.
• For every \(i\) with \(1\le i\le n\), the adjacent pair \(\left(a_{2i-1}, a_{2i}\right)\) satisfies \(a_{2i-1} < a_{2i}\).

Your task is to compute the number of different interesting sequences of length \(2n\). Since the answer can be very large, output it modulo \(p\), where \(p\) is a given modulus.

Hint: It can be shown that the answer is the \(n\)th Catalan number, given by:

\[ C_n = \frac{1}{n+1}\binom{2n}{n}. \]

inputFormat

The first and only line of input contains two integers \(n\) and \(p\) (separated by a space), where \(n\) is the half-length of the permutation and \(p\) is a prime number specifying the modulus.

outputFormat

Output a single integer: the number of interesting sequences modulo \(p\).

sample

1 1000000007

1