Description

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.

Input Format

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 Format

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

3 10000

9

4 10000

21

100 100000000

3107203

Hint

[Constraints]

Translated by ChatGPT 5