( a * b ) % p = ( a % p ) * ( b % p)

typedef long long LL;
LL qmi(LL a,LL b,LL p){
   LL ans=1%p;//如果是1，b为0时会出错
   a%=p;
    while(b){
        if(b&1) ans=(ans*a)%p;//判断b是否为奇数
        a=(a*a)%p;
        b>>=1;
    }
    return ans;
}