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

    }
    return ans * a % MOD;
}