Since UOJ is also lacking a head, and the AI for creating the next problem did not perform as expected, the Fish King Qingyu has retrained a new AI.

The Fish King Qingyu's AI refuses to work 996 hours and instead demands that Qingyu play a game with it.

The AI has generated $n$ problems, numbered $1, 2, \dots, n$. The AI has chosen one of these problems in its mind, but Qingyu does not know which one it is.

Qingyu can ask the AI several questions. Each question is of the form: given $l, r$ such that $1 \le l \le r \le n$, ask whether the number of the chosen problem is in the range $[l, r]$.

If Qingyu can uniquely determine the number of the problem by asking these questions simultaneously, then Qingyu wins. Otherwise, the AI wins.

Obviously, as the Fish King, Qingyu's intelligence is not inferior to the AI. Therefore, you can assume that both Qingyu and the AI are perfectly rational.

Now, Qingyu has captured you and demands that you calculate how many ways Qingyu can ask questions such that he is guaranteed to win. Two schemes are considered different if and only if there exists an interval $[l, r]$ that is asked in one scheme but not in the other.

Additionally, Qingyu practices benevolent governance, so he will not make things too difficult for you; you only need to provide the answer modulo a large prime $P$.

Input

The first line contains two positive integers, $n$ and $P$, with meanings as described in the problem statement.

Output

A single line containing a non-negative integer, representing the answer modulo the large prime $P$.

Examples

Input 1

3 998244353

Output 1

48

Input 2

7 999997543

Output 2

256097184

Input 3

100 1000000007

Output 3

402821964

Constraints

There are $10$ test cases in this problem, each worth an equal share of the points.

For test cases $1 \sim 2$, $n \le 6$.

For test cases $3 \sim 4$, $n \le 20$.

For test cases $5 \sim 6$, $n \le 80$.

For all test cases, $1 \le n \le 300$ and $10^8 \le P \le 10^9+7$.