long long int pow_mod(long long int a, long long int k)
{
    long long int ans = 1;
    a %= MOD;
    while(k)
    {
        if(k % 2) ans *= a;
        a = (a * a) % MOD;
        k /= 2;
        ans %= MOD;
    }
    return ans;
}