PW

#define MOD (1000000007)
ll pw(ll n,ll k){
    ll r(1);
    while(k){
        if(k&1)r*=n,r%=MOD;
        n*=n,n%=MOD;
        k>>=1;
    }
    return r;
}