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 1\,000\,000\,000~
2
3
4	~2 \le n \le 100~
5
6	~2 \le n \le 200~
7
8	~2 \le n \le 500~
9
10