Sushi Dinner

Time limit1sMemory limit1024 MB

Summary

Count pairs of subsets X and Y of {2, ..., n} where every x in X is coprime to every y in Y, modulo p.

Level: Medium7 of 10
Topics: Number theory, Dynamic programming, Bit manipulation
Solved: No attempts yet

Problem

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

Input

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

Output

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

Constraints

$2 \le n \le 500$
$0 < p \le 1\,000\,000\,000$

Examples3

Example 1
Input
```
3 10000
```
Expected output
```
9
```
Example 2
Input
```
4 10000
```
Expected output
```
21
```
Example 3
Input
```
100 100000000
```
Expected output
```
3107203
```