M1 - 快速幂与龟速乘

typedef long long llong;

llong qpow(llong x, llong a, llong mod) {
	static llong ret;
	ret = 1;
	while (a) {
		if (a & 1u) (ret *= x) %= mod;
		(x *= x) %= mod;
		a >>= 1u;
	}
	return ret;
}

typedef unsigned long long ullong;

ullong smul(ullong a, ullong b, ullong mod) {
	ullong ret = 0;
	while (b) {
		if (b & 1u) (ret += a) %= mod;
		(a <<= 1u) %= mod;
		b >>= 1u;
	}
	return ret;
}