Legend has it that long ago, a mysterious creature called a goblin lived on the earth.
Goblins love to live in continuous mountain ranges. Specifically, a mountain range $H$ of length $N$ can be divided into $N$ segments from left to right, each with a unique height $H_i$, where $H_i$ is a positive integer between $1$ and $N$.
If a mountain segment is higher than all its adjacent segments, it is a mountain peak. Segments at the edges have only one adjacent segment, while others have two (left and right).
Similarly, if a mountain segment is lower than all its adjacent segments, it is a mountain valley.
Goblins share a common hobby—drinking. Taverns can be built in mountain valleys. Goblin taverns are always bustling with noise day and night, and the aroma of goblin wine can drift for miles.
Goblins are also very vigilant creatures. They can build watchtowers on every mountain peak and take turns standing guard to ensure they are the first to know about any enemy invasion.
The goblins hope that each of the $N$ mountain segments can have either a watchtower or a tavern. Only a mountain range that satisfies this condition can be inhabited by goblins.
You want to know how many mountain ranges of length $N$ can be inhabited by goblins. Two mountain ranges $A$ and $B$ are different if and only if there exists an $i$ such that $A_i \neq B_i$. Since this number can be very large, you are only interested in the remainder when it is divided by $P$.
Input
The input contains a single line with two positive integers $N$ and $P$.
Output
The output contains a single line with a non-negative integer representing the result of your answer modulo $P$.
Examples
Input 1
4 7
Output 1
3
Note
There are 10 possible mountain ranges: 1324, 1423, 2143, 2314, 2413 3142, 3241, 3412, 4132, 4231 The underlined digits represent peaks where watchtowers can be built, and the others represent valleys where taverns can be built.
Constraints
For 20% of the data, $N \le 10$; For 40% of the data, $N \le 18$; For 70% of the data, $N \le 550$; For 100% of the data, $3 \le N \le 4200$, $P \le 10^9$.