Description

How many ways are there to put the numbers(1, 2, 3, ..., 2n) into a 2 * n array so that rows and columns are in increasing order from left to right and from top to bottom?

Every line we give n and m, we want to know the answer modulo m.

For example, one solution when n = 3 is

1 2 5
3 4 6

Input

There are multiple test cases.(the number of test cases <= 20)

Each test case contains two integer numbers n and m in a line.
(1 <= n <= 100000, 1 <= m <= 10^9)

Output

For each test case, output the number of ways modulo m in a line.

Sample Input

3 100
1 100

Sample Output

5
1

Author