/**
 * 计算a**b(mod c)
 * @param {bigInt} a 底数
 * @param {bigInt} b 指数
 * @param {bigInt} c 模
 * @returns {binInt}结果
 */
function fastPowerMod(a, b, c){
    let res = 1n 
    a %= c

    while (b) {
        if(b&1n){
            res = (res*a)%c
        }
        a = a*a%c
        b>>=1n
    }
    return res
}


/**
 * 检测一个大数是否是素数
 * @param {bigInt} n 被检测的大数
 * @returns {boolean} 是否是素数
 */
function isPrime(n){
    // 检测20次
    let a = n
    for(let i=0; i<20; i++){
        a >>= 1n// a取1/2n
        if(fastPowerMod(a, n-1n, n)!==1n){
            return false
        }
    }
    return true
}