众所周知，取模一次消耗的时间大约是一次乘法的20~40倍，我在某个地方看到一个取模优化，代码如下：

struct fastmod{
    unsigned long long b;
    __uint128_t m;
    fastmod(int mod):b(mod),m(((__uint128_t)1<<64)/mod){}
}mod=1e9+7;
unsigned long long operator %(unsigned long long a,fastmod b){
    unsigned long long q=a-(b.m*a>>64)*b.b;
    return q>=b.b?q-b.b:q;
}

已经检测过，没问题，但蒟蒻不会证明，求大佬证明