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; }