快速幂

long long pow_quick(long long a, long long n){
    long long res = 1;
    while(n){
        if(n & 1){
            res *= a;   //判断最后一位是不是1，如果是的话，就把 a 乘上来
        }
        a *= a;         //每一步都要乘a ，相当于a的平方
        n >>= 1;        //右移一位
    }
    return res;
}

快速幂取模

long long pow_quick(long long a, long long n, long long m){
    long long res = 1;
    while(n){
        if(n & 1){
            res = res * a % m;
        }
        a = a * a % m;
        n >>= 1;
    }
    return res;
}