To celebrate the successful opening of NOI, the organizers have prepared a sushi banquet. Xiao G and Xiao W, as participants of NOI, have also been invited to the sushi banquet.

At the banquet, the organizers provide $n-1$ different types of sushi, numbered $1, 2, 3, \dots, n-1$, where the $i$-th type of sushi has a deliciousness of $i+1$ (i.e., the deliciousness ranges from $2$ to $n$).

Now, Xiao G and Xiao W each wish to choose some types of sushi to taste. They define a tasting scheme as "disharmonious" if and only if: there exists a sushi with deliciousness $x$ among the types Xiao G tastes, and a sushi with deliciousness $y$ among the types Xiao W tastes, such that $x$ and $y$ are not coprime.

Xiao G and Xiao W wish to count the total number of "harmonious" sushi tasting schemes (modulo a given positive integer $p$). Note that a person may choose to eat no sushi at all.

Input

The first line contains two positive integers $n$ and $p$, separated by a single space, representing that there are $n$ types of sushi (with deliciousness up to $n$), and the final number of harmonious schemes should be taken modulo $p$.

Output

Output a single integer representing the result of the required number of schemes modulo $p$.

Constraints

Examples

Input 1

3 10000

Output 1

9

Input 2

4 10000

Output 2

21

Input 3

100 100000000

Output 3

3107203