Harmonious Sushi Tasting

To celebrate the successful opening of the NOI, the organizers are hosting a sushi dinner. Competitors Little G and Little W are invited to taste some sushi. The dinner offers (n-1) different types of sushi numbered (1,2,3,\dots,n-1). The sushi of type (i) has tastiness (i+1) (so the tastiness values range from (2) to (n)).

Little G and Little W will each choose a subset (possibly empty) of the sushi types. A tasting scheme is defined to be discordant if and only if there exists a sushi chosen by Little G with tastiness (x) and a sushi chosen by Little W with tastiness (y) such that (x) and (y) are not relatively prime (i.e. (\gcd(x,y)\neq 1)). In other words, the scheme is harmonious if for every pair (x) (in Little G’s selection) and (y) (in Little W’s selection), we have (\gcd(x,y)=1).

Calculate the number of harmonious tasting schemes modulo a given positive integer (p). Note that when a person does not choose any sushi, the scheme is automatically harmonious.

inputFormat

The input consists of a single line containing two positive integers (n) and (p), where (n) (with (n \ge 2)) denotes that there are (n-1) sushi types (with tastiness values from (2) to (n)), and (p) is the modulus.

outputFormat

Output a single integer, which is the number of harmonious tasting schemes modulo (p).

sample

2 1000

3