Domino rectangles P87164

You have $4n$ identical 3-3 domino pieces, and you must cover with them a $3 \times 3n$ rectangle. As you can see in the picture below, the positions $(2, 2), (2, 5), \dots, (2, 3n - 1)$ of the rectangle must be left empty. Depending on $n$, how many different rectangles are possible?

For instance, these are the two only possible rectangles for $n = 1$, two of the six possible rectangles for $n = 2$, and a possible rectangle for $n = 7$:

Input

Input consists of several cases, each with two integer numbers $n$ and $m$. You can assume $0 \le n \le 10^{12}$ and $2 \le m \le 10^6$.

Output

For every case, print the number of $3 \times 3n$ rectangles modulo $m$.