//最大公约数
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
//mk次方模p
int qmi(int m, int k, int p) {
    int res = 1 % p, t = m;
    while(k) {
        if(k & 1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}