Master _jl0x62_ loves bracelets very much. One day he travals to the land of Orz Pandas and goes to visit a souvenir shop. The Orz Pandas are selling a special kind of bracelets, named _the Orz Panda Bracelet_ (OPB) here. An OPB is a bracelet (cylindrical face) with length $n$, height $2$, and composed by some $1 times 2$ rectangular blocks. Certainly there would be $n$ blocks, for an OPB with length $n$.
Master _jl0x62_ will pay the Orz Pandas $n$ dollars for each OPB with length $n$. But he'll only pay for unique OPBs. Two OPBs are considered same if one coincides with another after a rotation about the axis passing through the center of the OPB and parallel in the direction of the OPB's height.
Due to a technical limitation, the Orz Pandas can only make OPBs with its length $n$ not greater than $m$. Please tell the Orz Pandas how many dollars they can get by selling the OPBs to Master _jl0x62_.
The Orz Pandas hate multi-precision numbers. So you should output the answer modulo an integer $p$.
There is only one test case in each input file.
The test case is a single line, containing two integers $m$ and $p$ seperated by a whitespace.
It's guaranteed that $1 <= m <= 10^9$, $1 <= p <= 10^9 + 9$.
It's *not* guaranteed that $p$ is a prime.
For each test case, output one line, containing the maximum amount of dollars the Orz Panda can get by selling the OPBs to _jl0x62_, modulo $p$.
For example, if $m = 2$, the Orz Pandas can make $1$ unique OPB with length $1$, and $3$ unique OPBs with length $2$. So they can get $1 times 1 + 3 times 2 = 7$ dollars.
The figure above shows the OPBs with length $2$. The subfigures labeled $1$, $2$, and $3$ represent three unique OPBs. The subfigure labeled $4$ represents the same OPB as subfigure $3$, but with a different cutting edge.
## Input
There is only one test case in each input file.The test case is a single line, containing two integers $m$ and $p$ seperated by a whitespace.It's guaranteed that $1 <= m <= 10^9$, $1 <= p <= 10^9 + 9$.It's *not* guaranteed that $p$ is a prime.
## Output
For each test case, output one line, containing the maximum amount of dollars the Orz Panda can get by selling the OPBs to _jl0x62_, modulo $p$.
[samples]
## Note
For example, if $m = 2$, the Orz Pandas can make $1$ unique OPB with length $1$, and $3$ unique OPBs with length $2$. So they can get $1 times 1 + 3 times 2 = 7$ dollars. The figure above shows the OPBs with length $2$. The subfigures labeled $1$, $2$, and $3$ represent three unique OPBs. The subfigure labeled $4$ represents the same OPB as subfigure $3$, but with a different cutting edge.
**Definitions**
Let $ f(i, r, P) $ denote the number of pairs $ (a, b) \in \mathbb{Z}_P^2 $ satisfying:
$$
a^r (b + b^2)^i \equiv b^i \pmod{P}
$$
where $ P $ is prime.
**Constraints**
1. $ 1 \le m \le 10^5 $
2. For each query:
- $ 10^5 \le Y < 10^9 + 7 $
- $ 1 \le N < P $
- $ 1 \le r \le 3 $
- $ 3 \le P < 10^9 + 7 $, and $ P $ is prime
**Objective**
For each query $ (Y, N, r, P) $, compute:
$$
\prod_{i=1}^{N} Y^{f(i, r, P)} \mod (10^9 + 7)
$$