ll fast_pow(ll a, ll b) {
    if (b == 0)
        return 1;
    ll res = fast_pow((a * a) % MOD, b / 2);
    if (b & 1)
        (res *= a) %= MOD;
    return res;
}