/*a*b (mod m) 的实现过程*/

/*当a,b很大的时候mod m就会产生溢出， 故运用乘法原理转换为加法求解*/

LL multi(LL a, LL b, LL m)

{

	LL exp = a %m, res = 0;

	while (b)

	{

		if (b & 1)  		//b的最低位是否为1

		{

			res = res + exp;

			if (res >= m)

				res = res -m;

		}

		exp = exp *2;

		if (exp > m)

			exp = exp - m;

		b >>= 1; 			//将b除以2

	}

	return res;

}