const int MOD = 1e9+7;
typedef long long ll;
ll ksc(ll a, ll b, ll p){
    ll res = 0;
    a %= p, b %= p;
    while(b){
        if(b&1)	res = (res + a) % p;
        a = (a << 1) % p;
        b >>= 1;
    }
    return res;
}
ll ksm(ll x, ll n, ll p){
    ll res = 1;
    while(n){
        if(n & 1)	res = ksc(res, x, p);
        x = ksc(x,x,p);
        n >>= 1;
    }
    return res;
}