Function modpow

codes/cpp/Code_4_06_6.cpp:8–16

long long fact[200009];

long long modpow(long long a, long long b, long long m) {
	// �J��Ԃ����@�ip �� a^1, a^2, a^4, a^8, ... �Ƃ������l���Ƃ�j
	long long p = a, Answer = 1;
	for (int i = 0; i < 30; i++) {
		if ((b & (1 << i)) != 0) { Answer *= p; Answer %= m; }
		p *= p; p %= m;
	}
	return Answer;
}

long long Division(long long a, long long b, long long m) {
	return (a * modpow(b, m - 2, m)) % m;