A sequence of positive integers $[a_1, \dots, a_m]$ of length $m$ is called good if and only if it satisfies the following properties:

1. $m \ne 0$, i.e., the sequence is non-empty.
2. $a_i > a_{i-1}$ for $2 \le i \le m$, i.e., the sequence is strictly increasing.
3. $1 \le a_i \le n$ for $1 \le i \le m$, i.e., all elements of the sequence are positive integers $\le n$.
4. $a_i \operatorname{xor} a_{i+1} \operatorname{xor} a_{i+2} \ne 0$ for $1 \le i \le m-2$, i.e., the XOR sum of any three consecutive terms in the sequence is not $0$.

Given $n$, count the total number of distinct good sequences. Two sequences are considered different if they have different lengths or if they have the same length but differ at some position. Output the answer modulo $mod$.

Input

A single line containing two positive integers $n$ and $mod$.

Output

Output a non-negative integer representing the answer.

Examples

Input 1

1 123456789

Output 1

1

Input 2

2 100000000

Output 2

3

Note 2

The sequences satisfying the conditions are $[1], [2], [1, 2]$.

Input 3

3 666666666

Output 3

6

Note 3

The sequences satisfying the conditions are $[1], [2], [3], [1, 2], [2, 3], [1, 3]$.

Input 4

5 987654321

Output 4

26

Input 5

322 998244353

Output 5

782852421

Constraints

There are 10 test cases, each worth 10 points. For all test cases, $1 \le n \le 10^6$ and $10^8 \le mod \le 10^9$. The detailed constraints are as follows: