//先进行预处理(反复平方法),在对指数进行讨论,再将预处理的结果更新到答案
int qmi(int a, int k, int p)
{
    int res = 1 % p;
    while(k)
    {
        if(k & 1)   res = res * a % p;
        k >>= 1;
        a = a * a % p;
    }
    return res;
}