MOD乗算のコード ・if文で分岐させることでモジュロ演算をしない(PGOが備わってれば分岐数の少ないif文は低コスト) ・bit毎に確認するので計算量はO(log(N))

mod_mult.cpp

const int MOD = 1000000007;

long long
mod_mult(long long a,long long b)
{
  long long res = 0;
	long long mir = a%MOD;
	while (b) {
		if (b&1) {
			res += mir;
			if (res > MOD) {
				res -= MOD;
			}
		}
		mir <<= 1;
		if (mir > MOD) {
			mir -= MOD;
		}
		b >>= 1;
	}
	return res;
}