Count the number of unlabeled unrooted trees with $n$ nodes that satisfy the following requirements:

1. Each node is one of three colors: red, blue, or yellow.
2. The degree of a red node is at most $4$, and the degree of both blue and yellow nodes is at most $3$.
3. Yellow nodes cannot be adjacent.

Note that unlabeled unrooted trees means: two trees are considered the same if one can be relabeled such that the corresponding nodes have the same colors and the edges are identical.

The answer should be modulo the given prime $P$.

Input

Two integers $n$ and $P$, as described in the problem statement.

Output

A single integer representing the number of valid trees modulo $P$.

Constraints

For $100\%$ of the data, $1 \le n \le 3000$ and $9 \times 10^8 \le P \le 1.01 \times 10^9$.

Examples

Input 1

2 998244353

Output 1

5

Input 2

3 998244353

Output 2

15

Input 3

20 998244353

Output 3

578067492