// compute (x^m)%k 
int pow(int x,int m, int k)
{
	if(m==0) return 1;
	else if(m&1) return pow(x,m-1,k)*x%k;
	else {
		int t=pow(x,m/2,k);
		return t*t%k;
	}
}

// compute (x^m)%k int pow(int x,int m, int k) { if(m==0) return 1; else if(m&1) return pow(x,m-1,k)*x%k; else { int t=pow(x,m/2,k); return t*t%k; } }