Compute the number of ways to choose two subsets $X,Y\subseteq \{2,3,\dots ,n\}$ such that there does not exist $x\in X,y\in Y$ such that $x$ and $y$ are not relatively prime. The sets $X,Y$ may be empty. Output the number of ways modulo $p$.

Input Specification

The input contains the integer $n$ and the modulo $p$ separated by a space.

Output Specification

Output the number of ways to choose the subsets $X,Y\subseteq \{2,3,\dots ,n\}$ satisfying the condition above.

Sample Input 1

3 10000

Sample Output 1

9

Sample Input 2

4 10000

Sample Output 2

21

Sample Input 3

100 100000000

Sample Output 3

3107203

Constraints

Test Case	$n$	Additional Constraints
1	$2\le n\le 30$	$0<p\le 1000000000$
2
3
4	$2\le n\le 100$
5
6	$2\le n\le 200$
7
8	$2\le n\le 500$
9
10