P2150 [NOI2015] Sushi Dinner

To celebrate the successful opening of NOI, the organizers prepared a sushi dinner. Xiao G and Xiao W, as NOI contestants, were invited to attend. At the dinner, the organizers provided $n - 1$ different types of sushi, numbered $1, 2, 3, \ldots, n - 1$, where the tastiness of the $i$-th type is $i + 1$ (that is, tastiness values range from $2$ to $n$). Now Xiao G and Xiao W each want to choose some types of sushi to taste. A tasting plan is called discordant if and only if: there exists a sushi with tastiness $x$ chosen by Xiao G and a sushi with tastiness $y$ chosen by Xiao W such that $x$ and $y$ are not coprime. They want to count how many harmonious tasting plans there are (i.e., plans that are not discordant), modulo a given positive integer $p$. Note that a person may choose no sushi.

The first line contains two positive integers $n, p$ separated by a single space. There are $n - 1$ types of sushi in total, with tastiness values from $2$ to $n$, and the final answer should be taken modulo $p$.

Output a single integer, which is the number of harmonious plans modulo $p$.

[Constraints] | Test point ID | Range of $n$ | Convention | |:-------------:|:--------------------:|:------------------------------------:| | 1 | $2 \le n \le 30$ | $0 < p \le 1{,}000{,}000{,}000$ | | 2 | Same as above. | Same as above. | | 3 | Same as above. | Same as above. | | 4 | $2 \le n \le 100$ | Same as above. | | 5 | Same as above. | Same as above. | | 6 | $2 \le n \le 200$ | Same as above. | | 7 | Same as above. | Same as above. | | 8 | $2 \le n \le 500$ | Same as above. | | 9 | Same as above. | Same as above. | | 10 | Same as above. | Same as above. | Translated by ChatGPT 5