用龟速乘或者__int128（目前NOI系列赛事已允许使用，包括csp和NOIP）,龟速乘代码：

LL mul(LL a,LL b,LL p){
    
    LL ans = 0;
    
    while (b){
        
        if (b & 1) ans = (ans + a) % p;
        a = (a + a) % p;
        b >>= 1;
        
    }
    
    return ans;
}

个人认为上面这一段仅为针对特殊情况给出的非重要和考察点的代码，而非题解，若有违规，将自行删除