ModMulLL

Calculate a· bbmod c (or a^b bmod c) for 0 ≤ a, b ≤ c ≤ 7.2· 10^18.

Time: O(1) for modmul, O(log b) for modpow 11 lines stress-tested, proven correct

content/number-theory/ModMulLL.h — chilli, Ramchandra Apte, Noam527, Simon Lindholm, source: https://github.com/RamchandraApte/OmniTemplate/blob/master/src/number_theory/modulo.hpp

typedef unsigned long long ull;
ull modmul(ull a, ull b, ull M) {
	ll ret = a * b - M * ull(1.L / M * a * b);
	return ret + M * (ret < 0) - M * (ret >= (ll)M);
}
ull modpow(ull b, ull e, ull mod) {
	ull ans = 1;
	for (; e; b = modmul(b, b, mod), e /= 2)
		if (e & 1) ans = modmul(ans, b, mod);
	return ans;
}