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

힌트