A permutation $P_1, P_2, \dots, P_n$ of $1, 2, \dots, n$ is called Magic if and only if: $\forall 2 \le i \le n, P_i > P_{\lfloor i/2 \rfloor}$.
Your task is very simple: calculate how many permutations of $1, 2, \dots, n$ are Magic. Since the answer may be very large, you only need to output the value modulo $p$.
Input
The first line of the input contains two integers $n$ and $p$, as defined above.
Output
The output contains a single integer, representing the number of Magic permutations of $1, 2, \dots, n$ modulo $p$.
Constraints
- 30% of the data: $1 \le n \le 10$;
- 100% of the data: $1 \le n \le 10^6, p \le 10^9$, $p$ is a prime number.
Examples
Input 1
20 23
Output 1
16