//a^n mod m
int exp_mod(int a,int n,int m){

    //x*y mod m = ((x%m) * (y%m))%m
    if(n == 1)
        return a % m;
    else if(n == 0)
        return 1 % m;
    if(n&1){//奇数 a^n = (a^(n-1))*a
        return ((a%m)*exp_mod(a,n-1,m)) % m;
    }
    else{//偶数 a^n = (a^(n>>1))^2
        int t = exp_mod(a,n>>1,m);
        return (t*t) % m;
    }
}