Problem Statement

You are given an integer $n$ greater than or equal to $2$ and a positive integer $m$.

A point $(x,y)$ on the plane that simultaneously satisfies the following $2$ conditions is called a good point.

• $x,y$ are both positive integers
• $x+y$ is an even number less than or equal to $2n$

Since there are finitely many good points, let $k$ be their number. Let $V = \lbrace (x_1,y_1),(x_2,y_2),\ldots,(x_k,y_k)\rbrace$ be the set of all good points, and let $v_i\coloneqq(x_i,y_i)$. In particular, $(1,1)$ is always a good point, and we let $v_1=(1,1)$.

Construct a simple undirected graph $G$ with vertex set $V$ as follows.

• For all integers $i,j$ with $1\leq i,j\leq k$, an edge connecting $v_i$ and $v_j$ exists if and only if $\lvert x_i-x_j\rvert + \lvert y_i-y_j\rvert = 2$

A spanning tree $T$ of $G$ that simultaneously satisfies the following $2$ conditions is called a good spanning tree.

• For all $i=1,2,\ldots,k$, vertex $v_i$ can be reached from vertex $v_1$ by traversing edges contained in $T$ exactly $\dfrac{x_i+y_i}{2}-1$ times
• Let $L_{i,j}$ be the line segment with endpoints at vertices $v_i,v_j$ ($i\neq j$). For any $2$ distinct edges $\lbrace v_a,v_b\rbrace,\lbrace v_c,v_d\rbrace$ contained in $T$, $L_{a,b}$ and $L_{c,d}$ have no common point other than at their endpoints

For a good spanning tree $T$, let $f(T)$ be the product of the $x$-coordinates of the vertices of degree $1$ in $T$.

Find the sum of $f(T)$ over all good spanning trees $T$, modulo $m$.

Input

The input is given from standard input in the following format.

$n$ $m$

• All inputs are integers
• $2\leq n\leq 5\times 10 ^ 6$
• $1\leq m\leq 10 ^ 9$

Output

Print the sum of $f(T)$ over all good spanning trees $T$, modulo $m$, on $1$ line, followed by a newline.

Sample

Sample 1

Input

2 12

Output

6

The graph $G$ for $n=2$ is shown on the left side of the figure below.

For this $G$, the only good spanning tree is the one shown on the right side of the figure. To read the figure: the edges drawn as solid red lines are the edges contained in the spanning tree.

In this spanning tree, the vertices of degree $1$ are the $3$ vertices $(1,3),(2,2),(3,1)$ painted black, whose $x$-coordinates are $1,2,3$ respectively. Thus $f(T)$ for this spanning tree $T$ is $1\cdot 2\cdot 3 = 6$, and the answer for this case is $6$.

Sample 2

Input

3 31415

Output

1200

The graph $G$ for $n=3$ is shown on the left side of the figure below.

An example of a good spanning tree for this $G$ is shown on the right side of the figure. In this spanning tree $T$, the vertices of degree $1$ are the $6$ vertices $(1,5),(2,2),(2,4),(3,3),(4,2),(5,1)$, so $f(T) = 1\cdot 2 ^ 2 \cdot 3 \cdot 4\cdot 5 = 240$.

Note that a spanning tree such as the one shown in the figure below is not a good spanning tree.

4 1

0

436279 998244353

227931850