long long get_pow(long long a, long long b) {
    long long ans = 1;
    while (b > 1) {
        if (b % 2 == 1)
            ans *= a;
        a *= a;
        b /= 2;

        ans %= MOD;          //беру по модулю все переменные,
        a %= MOD;            //которые изменяла
    }
    return ans * a % MOD;    //не волнуюсь за переполнение, потому что ans и a - уже взяты по модулю
}