25079번 - 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$