407672: GYM102870 B Bracelets of Orz Pandas

Memory Limit:256 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Bracelets of Orz Pandastime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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$$$.

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

ExamplesInput
1 114514
Output
1
Input
2 1919810
Output
7
Input
3 1000000007
Output
13
Input
4 998244353
Output
29
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.

加入题单

上一题 下一题 算法标签: