At a family banquet, an elderly person wore a very beautiful and unique necklace. There were many gemstones on it, each with a different color and shape. Each gemstone was very precious, shining with colorful light under the illumination, crystal clear and brilliant. Observing this unique necklace closely, there is either a gold bead or a silver bead between every two adjacent gemstones. The arrangement of the gold beads on the necklace satisfies a very special rule: no two gold beads on the necklace are adjacent to each other. If two gemstone necklaces have the same arrangement of gemstones, but the number or positions of the gold beads on the necklace are different, they are considered to be two different gemstone necklaces.

For example, when there are 6 gemstones of different colors and shapes on the necklace, and there is either a gold bead or a silver bead between every two adjacent gemstones, according to the rule that gold beads cannot be adjacent:

• When there is only 1 gold bead on the necklace, there are 6 different gemstone necklaces.
• When there are 3 gold beads on the necklace, there are only 2 different gemstone necklaces.

From this, we can know that when there is an odd number of gold beads on the necklace, there are a total of 8 different gemstone necklaces.

Gemstone Necklace Problem: For a given positive integer $n$, there are $n$ gemstones of different colors and shapes on a gemstone necklace. Between every two adjacent gemstones, there is either a gold bead or a silver bead, and the gold beads satisfy the rule of not being adjacent. For a fixed arrangement of gemstones, calculate how many different gemstone necklaces can be formed such that there is an odd number of gold beads on the necklace.

Input

The input contains multiple test cases.

Each line contains two positive integers $n$ and $m$, where $n$ represents the number of gemstones on the necklace, and $m$ is the modulo.

Output

For each test case, output the number of different gemstone necklaces with an odd number of gold beads, modulo $m$. Output one integer per line.

Examples

Input 1

4 1007
6 1007

Output 1

4
8

Constraints

• For $30\%$ of the test data, $1 \le n \le 500$.
• For $70\%$ of the test data, $1 \le n \le 20000$.
• For $100\%$ of the test data, $1 \le n \le 120000$.
• All test data satisfy $2 \le m \le 10^{10}$.