Matches Puzzle Game

As an exciting puzzle game for kids and girlfriends, the Matches Puzzle Game asks the player to find the number of possible equations $A - B = C$ with exactly $n~(5\le n\le 500)$ matches (or sticks).

In these equations, $A,B$ and $C$ are positive integers. The equality sign needs two matches and the sign of subtraction needs just one. Leading zeros are not allowed.

Please answer the number, modulo a given integer $m~(3\le m\le 2\times 10^9)$.

The input contains several test cases. The first line of the input is a single integer $t$ which is the number of test cases. Then $t~(1\le t\le 30)$ test cases follow.

Each test case contains one line with two integers $n~(5\le n\le 500)$ and $m~(3\le m\le 2\times 10^9)$.

For each test case, you should output the answer modulo $m$.

4
12 1000000007
17 1000000007
20 1000000007
147 1000000007

Case #1: 1
Case #2: 5
Case #3: 38
Case #4: 815630825

2015 ACM/ICPC Asia Regional Shenyang Online