typedef unsigned __int64 u64;

// a * b % n ( a, b, n < 2^54 )
u64 mod(u64 a, u64 b, u64 n)
{
	u64 a1 = (a & 0x7ffffff), a2 = (a >> 27);
	u64 b1 = (b & 0x7ffffff), b2 = (b >> 27);
	u64 r1 = a2 * b2;
	u64 r2 = a2 * b1;
	u64 r3 = a1 * b2;
	u64 r4 = a1 * b1;
	for(int i = 0;i < 54;i ++){
		r1 <<= 1;
		if(r1 >= n)
			r1 -= n;
	}
	for(int j = 0;j < 27;j ++){
		r2 <<= 1;
		if(r2 >= n)
			r2 -= n;
		r3 <<= 1;
		if(r3 >= n)
			r3 -= n;
	}
	return (r1 + r2 + r3 + r4) % n;
}