407672: GYM102870 B Bracelets of Orz Pandas

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 \leq m \leq 10^9$$$, $$$1 \leq p \leq 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$$$.

1 114514

1

2 1919810

7

3 1000000007

13

4 998244353

29

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.