Sushi Dinner

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$.

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

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

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