flirly 精通数学，经常研究数学问题。对于质数这种问题更是无敌。 
对于N个不同的质数P1,P2.....Pn，用这些质数作为项（允许重复），任意组成一个数列，使这个数列的任一连续项的乘积不是完全平方数。 
求出这种数列的项数的最大值,flirly想知道这个值的大小，由于结果可能很大，只需要输出对一个给定正整数m取模后的结果即可。你知道这个 
结果吗？ 
 

输入格式

输入包含多组数据，每组数据由单独的一行组成，包括两个整数N和M(0<=N<= 1000000, 0<=M<= 50000)。

输出格式

每组数据输出单独的一行，表示这种数列的项数的最大值。

样例输入

2 10000

样例输出

3

//快速幂 
#include<stdio.h>
int m;
int power(int a,int n){
	if(n==0) return 1;
	if(n==1) return a%m;
	if(n%2==0) return (power((a%m)*(a%m),n/2)%m);
	if(n%2==1) return ((a%m)*(power((a%m),n-1)%m)%m);
}
int main(){
	int n,res;
	while(scanf("%d %d",&n,&m)!=EOF){
		/*res=1;
		for(int i=2;i<=n;i++){
			res=(2*res+1)%m;
		}
		printf("%d\n",res);*/
		if(n==0) res=0;
		else{
			res=power(2,n);
			if(res==0)
			res=m-1;
			else
			res=res-1;
		}
		printf("%d\n",res);
	}
	return 0;
}