Problem Description

To celebrate the successful opening of NOI, the organizers have prepared a sushi dinner for everyone. Xiao G and Xiao W, as contestants participating in NOI, were also invited to the sushi dinner.

At the dinner, the organizers provided $n-1$ different types of sushi, numbered $1, 2, 3, \ldots, n-1$, where the deliciousness of the $i$-th type of sushi is $i+1$ (i.e., the deliciousness ranges from $2$ to $n$).

Now, Xiao G and Xiao W want to each select some types of sushi to taste. They define a tasting scheme as harmonious if and only if: there exists a type of sushi with deliciousness $x$ that Xiao G tastes, and a type of sushi with deliciousness $y$ that Xiao W tastes, such that $x$ and $y$ are not coprime.

Xiao G and Xiao W now want to count how many harmonious tasting schemes there are (modulo a given positive integer $p$). Note that a person can choose not to eat any sushi.

Input Format

The first line of the input file contains two positive integers $n$ and $p$, separated by a single space, indicating that there are $n$ types of sushi and the number of harmonious schemes needs to be taken modulo $p$.

Output Format

Output a single line containing one integer, which is the result of the number of harmonious schemes modulo $p$.

Sample Input and Output

Sample Input #1

3 10000

Sample Output #1

9

Sample Input #2

4 10000

Sample Output #2

21

Sample Input #3

100 100000000

Sample Output #3

3107203

Notes

Data Range

Correction: $0 < p \le 10^9$

见题面 Input 部分

见题面 Output 部分