void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;

    ll ans = 0;
    rep2(i, 1, N + 1) {
        ans += intpow(-1, i) * intpow(i, 3);
    }
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;
    vll A(N);
    rep(i, N) cin >> A[i];

    vint P(N);
    iota(all(P), 1);

    do {
        int ok = 1;
        rep(i, N) {
            if (A[i] == -1) continue;
            if (A[i] != P[i]) ok = 0;
        }
        if (ok) {
            Yes();
            print(P);
            return;
        }
    } while (next_permutation(all(P)));

    No();
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    vint v(3);
    rep(i, 3) cin >> v[i];
    sort(all(v));

    yesno(v[0] == v[1] || v[1] == v[2]);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, M, K;
    cin >> N >> M >> K;
    vint A(K), B(K);
    rep(i, K) {
        cin >> A[i] >> B[i];
        A[i]--, B[i]--;
    }

    vvint sol(N, vint(M));
    vint ans;
    rep(i, K) {
        sol[A[i]][B[i]] = 1;

        int cnt = 0;
        rep(j, M) if (sol[A[i]][j]) cnt++;
        if (cnt == M) ans.push_back(A[i] + 1);
    }

    print(ans);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    modint::set_mod(10000);
    using mint = modint;

    auto f = [&](string X, ll MOD) -> mint {
        int N = X.size();

        // dp[is_less][prev number][dir][mod]
        // dir: 0 不定, 1 up, 2 down
        vector dp(2, vector(10, vector(3, vector<mint>(MOD))));
        dp[0][0][0][0] = 1;

        rep(i, N) {
            int t = X[i] - '0';
            vector dpn(2, vector(10, vector(3, vector<mint>(MOD))));

            rep(d, 10) rep(is_less, 2) rep(prev_number, 10) rep(dir, 3) rep(mod, MOD) {
                if (!is_less && d > t) continue;
                if (dir == 1 && prev_number <= d) continue;
                if (dir == 2 && prev_number >= d) continue;
                if (dir == 0 && d != 0 && prev_number == d) continue;

                int is_less_n = is_less || d < t;
                int dir_n = 0;
                if (dir == 0 && prev_number == 0) {
                    dir_n = 0;
                } else if (prev_number < d) {
                    dir_n = 1;
                } else if (prev_number > d) {
                    dir_n = 2;
                }

                int mod_n = (mod * 10 + d) % MOD;

                dpn[is_less_n][d][dir_n][mod_n] += dp[is_less][prev_number][dir][mod];
            }

            swap(dp, dpn);
        }

        mint ans = 0;
        rep(is_less, 2) rep(d, 10) rep(dir, 3) {
            ans += dp[is_less][d][dir][0];
        }

        // cout << ans << endl;

        return ans;
    };

    string A, B;
    ll M;
    cin >> A >> B >> M;

    ll zigzag = 0;
    {
        ll m = (A[0] - '0') % M;
        rep2(i, 1, (ll)A.size()) {
            m *= 10;
            m += A[i] - '0';
            m %= M;
        }

        int ok = 1;
        rep(i, (ll)A.size() - 1) {
            if (A[i] == A[i + 1]) {
                ok = 0;
                break;
            }
        }
        rep2(i, 1, (ll)A.size() - 1) {
            if (A[i - 1] < A[i] && A[i] < A[i + 1]) ok = 0;
            if (A[i - 1] > A[i] && A[i] > A[i + 1]) ok = 0;
        }
        zigzag = m == 0 && ok;
    }

    mint ans = f(B, M) - f(A, M) + zigzag;
    cout << ans.val() << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string L;
    cin >> L;

    // dp[is_less]
    vector<mint> dp(2);
    dp[0] = 1;

    int N = L.size();
    rep(i, N) {
        int t = L[i] - '0';
        vector<mint> dpn(2);

        rep(d, 2) rep(is_less, 2) {
            if (!is_less && d > t) continue;

            int is_less_n = is_less || d < t;
            ll mul = d == 0 ? 1 : 2;

            dpn[is_less_n] += dp[is_less] * mul;
        }

        swap(dp, dpn);
    }

    cout << (dp[0] + dp[1]).val() << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll A, K;
    cin >> A >> K;

    string S = to_string(A);

    // dp[comp][used]
    // comp = 0: A と同じ
    // comp = 1: A より小さい
    // comp = 2: A より大きい
    // used: 使用した数の集合
    vector dp(3, vll(1 << 10, -1));
    dp[0][0] = 0;
    rep(j, 1 << 10) dp[2][j] = INF;

    int N = S.size();
    rep(i, N) {
        int t = S[i] - '0';
        vector dpn(3, vll(1 << 10, -1));
        rep(j, 1 << 10) dpn[2][j] = INF;

        rep(d, 10) rep(comp, 3) rep(used, 1 << 10) {
            if (dp[comp][used] < 0) continue;
            if (dp[comp][used] == INF) continue;
            int comp_n = comp;
            if (comp == 0) {
                if (d < t) comp_n = 1;
                if (d > t) comp_n = 2;
            }

            int used_n = used | (1 << d);
            if (used == 0 && d == 0) used_n = 0;  // 0 が続いている場合は 0 を使っていないとみなす

            if (comp_n <= 1) {
                chmax(dpn[comp_n][used_n], dp[comp][used] * 10 + d);
            } else {
                chmin(dpn[comp_n][used_n], dp[comp][used] * 10 + d);
            }
        }

        swap(dp, dpn);
    }

    ll ans = INF;
    {
        ll mx = 0;
        ll mi = INF;
        rep(used, 1 << 10) {
            if (__builtin_popcountll(used) > K) continue;
            chmax(mx, max(dp[0][used], dp[1][used]));
            chmin(mi, dp[2][used]);
        }
        chmin(ans, A - mx);
        chmin(ans, mi - A);
    }

    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll X, C;
    cin >> X >> C;

    ll ans = X / (1000 + C) * 1000;
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;

    vint keys(N);
    rep(i, N) cin >> keys[i];

    vll visited(N + 1);
    visited[0] = visited[N] = 1;

    rep(i, N) {
        if (keys[i] == 0) {
            visited[i + 1] = 1;
        } else {
            break;
        }
    }

    for (int i = N - 1; i >= 0; i--) {
        if (keys[i] == 0)
            visited[i] = 1;
        else
            break;
    }

    ll cnt = 0;
    rep(i, N + 1) if (!visited[i]) cnt++;
    cout << cnt << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int i, j;
    char c;
    cin >> i >> c >> j;
    if (j == 8) {
        i++;
        j = 1;
    } else {
        j++;
    }
    cout << i << '-' << j << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int H, W;
    cin >> H >> W;
    vector<string> grid(H);
    rep(i, H) cin >> grid[i];

    vint di = {0, 1, 0, -1};
    vint dj = {1, 0, -1, 0};

    int ok = 1;
    rep(i, H) rep(j, W) {
        if (grid[i][j] == '.') continue;

        int cnt = 0;
        rep(d, 4) {
            int ni = i + di[d], nj = j + dj[d];
            if (clamp(ni, 0, H - 1) != ni || clamp(nj, 0, W - 1) != nj) continue;
            if (grid[ni][nj] == '#') cnt++;
        }
        if (cnt == 2 || cnt == 4) continue;
        ok = 0;
    }
    yesno(ok);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<string> S(N);
    rep(i, N) cin >> S[i];

    int X;
    string Y;
    cin >> X >> Y;
    X--;

    yesno(S[X] == Y);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll X, Y;
    cin >> X >> Y;

    auto f = [](ll x) -> ll {
        string s = to_string(x);
        reverse(all(s));
        ll ret = stoll(s);
        return ret;
    };

    vll A(11);
    A[1] = X, A[2] = Y;
    rep2(i, 3, 11) {
        A[i] = f(A[i - 1] + A[i - 2]);
    }
    cout << A[10] << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, M;
    cin >> N >> M;

    // dp[i][f]: i 番目の数が 0 番目の数と同じ(f=1)/違う(f=0)ときの場合の数
    vector dp(N, vector<mint>(2));
    dp[0][1] = M;
    rep2(i, 1, N) {
        // i 番目は 0 番目と同じ数字になる、かつ、同じ数字が連続してはいけないので i-1 番目の数は 0 番目の数とは違う
        dp[i][1] += dp[i - 1][0];

        // i 番目が 0 番目と異なる数字のとき、i-1 番目の数は 0 番目と同じか異なるのどちらでもいける。
        // i-1 番目の数が 0 番目と同じ時、i 番目の数は 0 番目とは違う M-1 通りが考えられる
        // i-1 番目の数が 0 番目と異なる時、i 番目の数は 0 番目とは異なり i-1 番目の数とも異なるから M-2 通りが考えられる
        dp[i][0] += dp[i - 1][1] * (M - 1) + dp[i - 1][0] * (M - 2);
    }
    cout << dp[N - 1][0].val() << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll X, Y;
    cin >> X >> Y;

    X += Y;
    X %= 12;

    if (X == 0) X = 12;
    cout << X << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, M;
    cin >> N >> M;
    vector<string> S(N);
    rep(i, N) cin >> S[i];

    vll scores(N);
    rep(j, M) {
        ll x = 0, y = 0;
        rep(i, N) {
            if (S[i][j] == '0')
                x++;
            else
                y++;
        }

        if (x == 0 || y == 0) {
            rep(i, N) scores[i]++;
            continue;
        }

        if (x < y) {
            rep(i, N) {
                if (S[i][j] == '0') scores[i]++;
            }
        } else {
            rep(i, N) {
                if (S[i][j] == '1') scores[i]++;
            }
        }
    }

    ll mx = 0;
    rep(i, N) {
        chmax(mx, scores[i]);
    }

    vll ans;
    rep(i, N) if (scores[i] == mx) ans.push_back(i + 1);
    print(ans);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    string S;
    cin >> N >> S;

    int m = S.size();
    int ok = 1;
    if (m < 3) {
        ok = 0;
    } else {
        string subs = S.substr(m - 3, 3);
        ok = subs == "tea";
    }

    yesno(ok);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string S;
    cin >> S;

    double ans = 0.0;
    int N = S.size();
    rep(i, N) rep2(j, i + 1, N) {
        if (S[i] == 't' && S[j] == 't' && j - i >= 2) {
            ll len = j - i + 1;
            ll x = 0;
            rep2(k, i, j + 1) if (S[k] == 't') x++;
            chmax(ans, (double)(x - 2) / (double)(len - 2));
        }
    }

    printf("%.15lf\n", ans);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, A, B;
    cin >> N >> A >> B;
    string S;
    cin >> S;

    for (int i = A; i < N - B; i++) cout << S[i];
    cout << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    multiset<ll> A;
    rep(i, N) {
        ll a;
        cin >> a;
        A.insert(a);
    }

    rep(i, M) {
        ll b;
        cin >> b;
        auto it = A.lower_bound(b);
        if (*it == b) {
            A.erase(it);
        }
    }

    vll ans;
    for (auto x : A) ans.push_back(x);
    print(ans);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll a, b, c;
    cin >> a >> b >> c;

    ll x = b * 2 - a - c;
    ll ans = 0;
    if (x >= 0) {
        ans = x;
    } else {
        x = abs(x);
        ll q = (x + 1) / 2;
        ll r = x % 2;
        ans = q + r;
    }
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, K;
    cin >> N >> K;
    vll v(N, K);

    vll L, R;

    rep(i, K) {
        char c;
        ll k;
        cin >> c >> k;
        k--;
        if (c == 'L') {
            L.push_back(k);
        } else {
            R.push_back(k);
        }
    }

    sort(rall(L));
    sort(rall(R));

    for (ll k : L) {
        rep(i, k) v[i]--;
    }
    for (ll k : R) {
        rep2(i, k + 1, N) v[i]--;
    }
    for (ll k : L) {
        v[k] = 1;
    }
    for (ll k : R) {
        v[k] = 1;
    }

    mint ans = 1;
    rep(i, N) ans *= v[i];
    cout << ans.val() << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    string S, T;
    cin >> S >> T;

    string U = string(N, '0');
    reverse(all(S));
    reverse(all(T));

    ll sd = 0, td = 0;
    rep(i, N) {
        sd += S[i] != U[i];
        td += T[i] != U[i];
    }
    if (sd == td) {
        cout << U << endl;
        return;
    }

    int ok = 0;
    rep(i, N) {
        ll tmps = sd, tmpt = td;
        if (S[i] == '1')
            tmps--;
        else
            tmps++;
        if (T[i] == '1')
            tmpt--;
        else
            tmpt++;

        if (abs(tmps - tmpt) < abs(sd - td)) {
            U[i] = '1';
            sd = tmps;
            td = tmpt;
        }

        if (sd == td) {
            ok = 1;
            break;
        }
    }

    reverse(all(U));
    string ans = U;
    if (!ok)
        ans = "-1";
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll A, B, C;
    cin >> A >> B >> C;

    vll v = {A, B, C};
    sort(all(v));

    ll ans = 0;
    if (v[0] < v[1]) {
        ll d = v[1] - v[0];
        ans += d;
        v[1] -= d;
        v[2] -= d;
    }

    if (v[1] < v[2]) {
        ll d = v[2] - v[1];
        ans += d * 2;
        v[0] -= d;
        v[1] -= d;
        v[2] -= d * 2;
    }

    if (v[0] >= 0 && v[0] == v[1] && v[1] == v[2]) {
        ans += v[0];
    } else {
        ans = -1;
    }
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, L, R;
    cin >> N >> L >> R;
    L--, R--;
    string S;
    cin >> S;
    int ok = 1;
    for (int i = L; i <= R; i++) {
        if (S[i] != 'o') ok = 0;
    }
    yesno(ok);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string S;
    cin >> S;

    int N = S.size();
    string T;
    T = S;
    rep(i, N) if (T[i] != '#') {
        T[i] = 'o';
    }

    rep(i, N) rep2(j, i + 1, N) {
        if (T[i] == 'o' && T[j] == 'o') {
            int has = 0;
            rep2(k, i + 1, j) if (T[k] == '#') has = 1;
            if (!has) T[j] = '.';
        }
    }

    cout << T << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;
    vll P(N);
    rep(i, N) cin >> P[i];

    int mx = (int)1e5 + 5;
    vector<bool> dp(mx);
    dp[0] = true;

    rep(i, N) {
        for (ll p = mx - 1; p >= 0; p--) {
            if (p - P[i] >= 0 && dp[p - P[i]]) {
                dp[p] = true;
            }
        }
    }

    ll ans = 0;
    rep(i, mx) ans += dp[i];
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;

    vll A(N), B(N);
    rep(i, N) cin >> A[i] >> B[i];

    vector<bool> fixed(1 << N), win(1 << N);

    // 使われたカードの状態が state のときに手番が来たときに勝てるか
    auto dfs = [&](auto dfs, int state = 0) -> bool {
        if (fixed[state]) return win[state];
        vector<bool> ret;
        // 表
        rep(i, N) rep2(j, i + 1, N) {
            if (!(state >> i & 1) && !(state >> j & 1) && A[i] == A[j]) {
                bool x = dfs(dfs, state | (1 << i) | (1 << j));
                ret.push_back(x);
            }
        }

        // 裏
        rep(i, N) rep2(j, i + 1, N) {
            if (!(state >> i & 1) && !(state >> j & 1) && B[i] == B[j]) {
                bool x = dfs(dfs, state | (1 << i) | (1 << j));
                ret.push_back(x);
            }
        }

        fixed[state] = true;
        for (bool x : ret) {
            if (!x) return win[state] = true;
        }
        return win[state] = false;
    };

    string ans = "Aoki";
    if (dfs(dfs)) ans = "Takahashi";
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;
    vll A(N);
    rep(i, N) cin >> A[i];
    ll X;
    cin >> X;

    int ok = 0;
    rep(i, N) if (A[i] == X) ok = 1;
    yesno(ok);
}

void solve() {
    ios base::sync_with_stdio(false);
    cin.tie(nullptr);

    string S;
    cin >> S;

    vll ids;
    rep(i, (ll)S.size()) {
        if (S[i] == '#') ids.push_back(i + 1);
    }

    for (ll i = 0; i < (ll)ids.size(); i += 2) {
        cout << ids[i] << ',' << ids[i + 1] << endl;
    }
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll X;
    cin >> X;

    // A^5 - B^5 = (A-B)(A^4 + A^3*B + A^2*B^2 + A*B^3 + B^4)
    for (ll d = 1; d * d <= X; d++) {
        if (X % d != 0) continue;
        ll t = X / d;
        for (ll a = 0; a * a * a * a <= t; a++) {
            ll b = a - d;
            if (a * a * a * a * a - b * b * b * b * b == X) {
                cout << a << ' ' << b << endl;
                return;
            }
        }
    }
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;

    ll ans = 0;
    for (ll r = 1; r * r <= N; r++) {
        if (N % r != 0) continue;
        ll m = N / r;
        m--;
        if (r < m) ans += m;
    }
    cout << ans << endl;
}

rep(i, v.size()) {
    v.pop_back();
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;
    vll A(N);
    rep(i, N) cin >> A[i];
    sort(all(A));

    vll f, b;
    rep(i, ceil(N, 2)) f.push_back(A[i]);
    rep2(i, ceil(N, 2), N) b.push_back(A[i]);

    int ok = 1;
    while (b.size()) {
        if (f.back() < b.back()) {
            f.pop_back();
            b.pop_back();
        } else {
            ok = 0;
            break;
        }
    }

    yesno(ok);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, L, R;
    cin >> N >> L >> R;

    ll ans = 0;
    rep(i, N) {
        int x, y;
        cin >> x >> y;
        if (x <= L && R <= y) ans++;
    }
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<pair<char, ll>> ps;
    ll tot = 0;
    rep(i, N) {
        char c;
        ll l;
        cin >> c >> l;
        ps.emplace_back(c, l);
        tot += l;
        if (tot > 100) {
            cout << "Too Long" << endl;
            return;
        }
    }

    for (auto [c, n] : ps) {
        rep(i, n) cout << c;
    }
    cout << endl;
}

vector<pair<char, long long int>> runLengthEncode(const string& input) {
    vector<pair<char, long long int>> encoded;
    int size = input.size();
    for (int i = 0; i < size; ++i) {
        long long int count = 1;
        while (i + 1 < size && input[i] == input[i + 1]) {
            ++i;
            ++count;
        }
        encoded.emplace_back(input[i], count);
    }
    return encoded;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    string S;
    cin >> N >> S;

    auto ps = runLengthEncode(S);
    ll ans = 0;
    for (auto [c, x] : ps) {
        if (c == '>')
            ans += (ll)x * (x + 1) / 2;
    }
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    auto cal = []() -> void {
        ll N, A, B;
        cin >> N >> A >> B;

        bool ans = true;
        if (A > N) ans = false;

        // ポーンは奇数行目、ルークは偶数行目に置くのが最適
        // ルークを偶数行目においてもまだ余っている場合は奇数行目におく
        // 開いてる行数 * (N-A) が B 以上であれば良い配置にできる。そうでなければできない。
        ll mx = (N + 1) / 2 * (N - A);
        if (A > N / 2) {
            mx -= (A - N / 2) * (N - A);
        }
        yesno(ans && B <= mx);
    };

    int t;
    cin >> t;
    rep(i, t) cal();
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, M;
    cin >> N >> M;
    vll A(M);
    rep(i, M) cin >> A[i];

    {
        int ok = 1;
        rep(i, M) {
            if (A[i] == 1 || A[i] == N) ok = 0;
        }
        if (!ok) {
            cout << -1 << endl;
            return;
        }
    }

    vll ans(N + 1, -1);
    vint used(N + 1);
    for (int a : A) {
        ans[a] = a + 1;
        used[a + 1] = 1;
    }

    queue<int> que;
    rep2(i, 1, N + 1) {
        if (!used[i]) que.push(i);
    }

    rep2(i, 1, N + 1) {
        if (ans[i] < 0) {
            ans[i] = que.front();
            que.pop();
        }
    }

    ans.erase(ans.begin(), ans.begin() + 1);
    print(ans);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    ll sum = 0;
    rep(i, N) {
        int a;
        cin >> a;
        sum += a;
    }
    yesno(sum <= M);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<string> S(N);
    rep(i, N) cin >> S[i];

    set<string> memo;
    rep(i, N) rep(j, N) {
        if (i == j) continue;
        memo.insert(S[i] + S[j]);
    }
    cout << memo.size() << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    string S;
    cin >> N >> S;

    S.push_back(S.back());

    mint ans = 1;
    ll cnt = 1;
    char p = S[0];
    rep2(i, 1, N + 1) {
        if (p == S[i]) {
            if (cnt >= 3) ans *= (cnt + 1) / 2;
            cnt = 1;
        } else {
            cnt++;
        }
        p = S[i];
    }
    cout << ans.val() << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    auto cal = []() -> void {
        int N;
        cin >> N;
        vint P(N);
        rep(i, N) {
            cin >> P[i];
            P[i]--;
        }

        vint v(N);
        iota(all(v), 0);

        if (v == P) {
            cout << 0 << endl;
            return;
        }

        int mx = -1;
        rep(i, N) {
            if (i == P[i] && mx < P[i]) {
                cout << 1 << endl;
                return;
            }
            chmax(mx, P[i]);
        }
        if (P.front() == N - 1 && P.back() == 0)
            cout << 3 << endl;
        else
            cout << 2 << endl;
    };

    int t;
    cin >> t;
    rep(i, t) cal();
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, K;
    cin >> N >> K;
    vint rem(N + 1, K);
    rem[0] = 0;
    vint ans;
    int x = (N + 1) / 2;
    if (N % 2 == 0) {
        ans.push_back(x);
        rem[x]--;
    } else {
        rep(i, K) {
            ans.push_back(x);
        }
        rem[x] = 0;
        x--;
        if (rem[x] > 0) {
            ans.push_back(x);
            rem[x]--;
        }
    }

    for (int x = N; x >= 1; x--) {
        rep(i, rem[x]) ans.push_back(x);
    }
    print(ans);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, M;
    cin >> N >> M;
    vll A(N), B(M);
    rep(i, N) cin >> A[i];
    rep(i, M) cin >> B[i];

    vint lid;
    int j = 0;
    rep(i, N) {
        if (A[i] == B[j]) {
            lid.push_back(i);
            j++;
        }
        if (j == M) break;
    }

    vint rid;
    j = M - 1;
    for (int i = N - 1; i >= 0; i--) {
        if (A[i] == B[j]) {
            rid.push_back(i);
            j--;
        }
        if (j < 0) break;
    }
    reverse(all(rid));

    yesno((ll)rid.size() == M && (ll)lid.size() == M && rid != lid);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;
    vll P(N);
    rep(i, N) {
        cin >> P[i];
        P[i]--;
    }
    string S;
    cin >> S;

    auto calL = [&]() -> mint {
        mint ret = 1;
        vint used(N);

        rep(i, N) {
            int now = P[i];
            int r = (P[i] + 1) % N;
            if (!used[r] && S[now] == 'R') {
                ret = 0;
            }
            if (used[r] && S[now] == '?') {
                ret *= 2;
            }
            used[now] = 1;
        }
        return ret;
    };

    auto calR = [&]() -> mint {
        mint ret = 1;
        vint used(N);

        rep(i, N) {
            int now = P[i];
            int l = P[i], r = (P[i] + 1) % N;
            if (!used[l] && S[now] == 'L') {
                ret = 0;
            }
            if (used[l] && S[now] == '?') {
                ret *= 2;
            }
            used[r] = 1;
        }
        return ret;
    };

    mint ans = calL() + calR();
    cout << ans.val() << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, C;
    cin >> N >> C;
    vll A(N);
    rep(i, N) cin >> A[i];

    vll cumsum(N + 1);
    rep(i, N) {
        cumsum[i + 1] = cumsum[i] + A[i];
    }

    ll ans = cumsum[N];

    {
        // max(f(l,r)) = max(f(0,r) - f(0,l))
        //             = max(f(0,r) - min_l (f(0,l)))
        ll t = -INF;
        ll mi = 0;

        rep2(i, 1, N + 1) {
            chmin(mi, cumsum[i - 1]);
            chmax(t, cumsum[i] - mi);
        }

        t *= (C - 1);
        t += cumsum[N];
        chmax(ans, t);
    }

    {
        // min(f(l,r)) = min(f(0,r) - f(0,l))
        //             = min(f(0,r) - max_l (f(0,l)))
        ll t = INF;
        ll mx = -INF;

        rep2(i, 1, N + 1) {
            chmax(mx, cumsum[i - 1]);
            chmin(t, cumsum[i] - mx);
        }

        t *= (C - 1);
        t += cumsum[N];
        chmax(ans, t);
    }
    cout << ans << endl;
}

┌─────────────────────┬─────────────────┐
│                     │                 │
│                     │                 │
│                     │                 │
│                     │                 │
│                     │                 │
│          1          │         2       │
│                     │                 │
│                     │                 │
│                     │                 │
│                     │                 │
├─────────────────────┼─────────────────┤
│                     │                 │
│                     │                 │
│          3          │         4       │
│                     │                 │
└─────────────────────┴─────────────────┘

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll H, W, N;
    cin >> H >> W >> N;
    vll A(N);
    rep(i, N) cin >> A[i];

    sort(rall(A));

    rep(i, N) {
        A[i] = 1 << A[i];
    }

    using P = tuple<ll, ll, ll>;
    priority_queue<P> pq;
    pq.push({min(H, W), H, W});

    int ok = 1;
    rep(i, N) {
        if (pq.size() == 0) {
            ok = 0;
            break;
        }
        auto [_, h, w] = pq.top();
        pq.pop();

        if (A[i] <= min(h, w)) {
            ll dw = w - A[i], dh = h - A[i];
            if (dw > 0) {
                pq.push({min(A[i], dw), A[i], dw});
            }
            if (dh > 0) {
                pq.push({min(dh, A[i]), dh, A[i]});
            }
            if (dw > 0 && dh > 0) {
                pq.push({min(dh, dw), dh, dw});
            }
        } else {
            ok = 0;
        }
    }

    yesno(ok);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<vector<pair<ll, ll>>> graph(N);
    vll C;
    rep(i, N - 1) {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        C.push_back(c);
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }

    vll dist(N);
    auto dfs = [&](auto dfs, int now, int p) -> void {
        for (auto [nx, c] : graph[now]) {
            if (nx == p) continue;
            dist[nx] = dist[now] + c;
            dfs(dfs, nx, now);
        }
    };

    dfs(dfs, 0, -1);
    int s = -1;
    ll d = -1;
    rep(i, N) {
        if (d < dist[i]) {
            d = dist[i];
            s = i;
        }
    }

    rep(i, N) dist[i] = 0;
    dfs(dfs, s, -1);
    d = -1;
    rep(i, N) {
        if (d < dist[i]) {
            d = dist[i];
        }
    }

    ll ans = accumulate(all(C), 0ll);
    ans *= 2;
    ans -= d;
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    auto cal = []() -> void {
        int N;
        cin >> N;
        vll S(N);
        rep(i, N) cin >> S[i];

        ll st = S[0], fin = S[N - 1];
        S.erase(S.begin(), S.begin() + 1);
        S.pop_back();

        sort(all(S));
        S.push_back(INF);

        ll ans = 2;
        ll pr = st;
        rep(i, (ll)S.size() - 1) {
            if (S[i] <= pr) continue;
            if (fin <= pr * 2) break;
            if (S[i] <= pr * 2 && S[i + 1] > pr * 2) {
                pr = S[i];
                ans++;
            }
        }
        if (fin > pr * 2) ans = -1;
        cout << ans << '\n';
    };

    int T;
    cin >> T;
    rep(i, T) {
        cal();
    }
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;
    vll P(N + 1);
    rep(i, N) cin >> P[i + 1];

    double INF = 100000;
    // dp[i][num]: i番目までの問題を選んで、num 個選んだときの \sum_{i=1}^k (0.9)^{k-i} Q[i] の最大値
    vector dp(N + 1, vector<double>(N + 1, -INF));
    dp[0][0] = 0;
    rep2(i, 1, N + 1) {
        rep(num, i + 1) {
            chmax(dp[i][num], dp[i - 1][num]);

            if (dp[i - 1][num] != -INF)
                chmax(dp[i][num + 1], dp[i - 1][num] * 0.9 + P[i]);
        }
    }

    vector<double> pow(N + 1), prd(N + 1);
    pow[0] = prd[0] = 1;
    rep2(i, 1, N + 1) {
        pow[i] = pow[i - 1] * 0.9;
        prd[i] += pow[i] + prd[i - 1];
    }

    double ans = -INF;
    rep2(num, 1, N + 1) {
        chmax(ans, dp[N][num] / prd[num - 1] - 1200.0 / sqrt(num));
    }
    printf("%.9lf\n", ans);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;
    vll A(N);
    rep(i, N) {
        cin >> A[i];
        A[i] %= 200;
    }

    map<int, vvint> mp;
    int n = min(N, 8ll);
    rep2(i, 1, 1 << n) {
        vint v;
        ll sum = 0;
        rep(j, n) if ((i >> j) & 1) {
            v.push_back(j + 1);
            sum += A[j];
        }
        sum %= 200;
        mp[sum].push_back(v);
    }

    for (auto [k, vv] : mp) {
        if (vv.size() >= 2) {
            Yes();
            rep(i, 2) {
                cout << vv[i].size() << ' ';
                print(vv[i]);
            }
            return;
        }
    }

    No();
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vll A(N);
    rep(i, N) cin >> A[i];

    vll cumsum(N + 1), mi(N + 1);
    rep(i, N) {
        cumsum[i + 1] = cumsum[i] + A[i];
    }

    ll ans = -INF;
    rep2(i, 1, N + 1) {
        chmax(ans, cumsum[i] - mi[i - 1]);
        mi[i] = min(mi[i - 1], cumsum[i]);
    }
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string P;
    int L;
    cin >> P >> L;
    yesno((int)P.size() >= L);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vll D(N);
    rep2(i, 1, N) cin >> D[i];

    rep(i, N) {
        ll sum = 0;
        vll ans;
        rep2(j, i + 1, N) {
            sum += D[j];
            ans.push_back(sum);
        }
        print(ans);
    }
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    string S;
    cin >> S;

    if (S.size() == 2) {
        yesno(S[0] == S[1]);
        return;
    }

    yesno(!(S.front() == 'A' && S.back() == 'B'));
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, K;
    cin >> N >> K;
    vll A(N);
    rep(i, N) cin >> A[i];

    auto f = [&](ll x) -> ll {
        ll ret = 0;
        for (ll a : A) ret += (a + x - 1) / x - 1;
        return ret;
    };

    ll ac = INF, wa = 0;
    while (ac - wa > 1) {
        ll wj = (ac + wa) / 2;
        if (f(wj) <= K) {
            ac = wj;
        } else {
            wa = wj;
        }
    }
    cout << ac << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, K;
    cin >> N >> K;
    vll A(N);
    rep(i, N) cin >> A[i];

    auto f = [&](ll x) -> bool {
        ll cnt = 0;
        rep(i, N) {
            cnt += min(A[i], x);
        }
        return cnt < K;
    };

    ll ac = 0, wa = INF;
    while (abs(ac - wa) > 1) {
        ll wj = (ac + wa) / 2;
        if (f(wj)) {
            ac = wj;
        } else {
            wa = wj;
        }
    }

    rep(i, N) {
        ll x = A[i];
        K -= min(x, ac);
        A[i] -= min(x, ac);
    }

    int i = 0;
    while (K) {
        if (A[i] > 0) {
            K--;
            A[i]--;
        }
        i++;
    }
    print(A);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, Q;
    cin >> N >> Q;
    vint col(N);
    rep(i, N) cin >> col[i];
    vector<set<int>> balls(N);
    rep(i, N) balls[i].insert(col[i]);

    rep(i, Q) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        if (balls[a].size() < balls[b].size()) {
            for (ll x : balls[a]) balls[b].insert(x);
            balls[a].clear();
        } else {
            for (ll x : balls[b]) balls[a].insert(x);
            balls[b].clear();
            swap(balls[a], balls[b]);
        }
        cout << balls[b].size() << endl;
    }
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, M;
    cin >> N >> M;
    using P = pair<ll, ll>;
    vector<vector<P>> graph(N);
    rep(i, M) {
        ll u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        graph[u].emplace_back(v, w);
    }

    vector used(N, vint(1 << 10, 0));
    used[0][0] = true;

    auto dfs = [&](auto dfs, int now, ll xor_sum) -> void {
        for (auto [nx, w] : graph[now]) {
            ll nx_xor_sum = xor_sum ^ w;
            if (used[nx][nx_xor_sum]) continue;
            used[nx][nx_xor_sum] = true;
            dfs(dfs, nx, nx_xor_sum);
        }
    };

    dfs(dfs, 0, 0);

    ll ans = INF;
    rep(i, 1 << 10) {
        if (used[N - 1][i]) chmin(ans, i);
    }
    if (ans == INF) ans = -1;
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<tuple<ll, ll, ll>> nodes;
    rep(i, N) {
        ll x, y, P;
        cin >> x >> y >> P;
        nodes.emplace_back(x, y, P);
    }

    auto f = [&](ll x) -> bool {
        rep(s, N) {
            vector<bool> used(N);
            used[s] = true;
            queue<int> que;
            que.push(s);
            while (que.size()) {
                int now = que.front();
                que.pop();

                rep(nx, N) {
                    if (nx == now) continue;
                    if (used[nx]) continue;
                    auto [xi, yi, pi] = nodes[now];
                    auto [xj, yj, pj] = nodes[nx];
                    if (pi * x >= abs(xi - xj) + abs(yi - yj)) {
                        used[nx] = true;
                        que.push(nx);
                    }
                }
            }

            ll sum = accumulate(all(used), 0);
            if (sum == N) return true;
        }
        return false;
    };

    ll ac = 0;
    rep(i, N) rep(j, N) {
        auto [xi, yi, pi] = nodes[i];
        auto [xj, yj, pj] = nodes[j];
        chmax(ac, abs(xi - xj) + abs(yi - yj));
    }

    ll wa = -1;
    while (ac - wa > 1) {
        ll wj = (ac + wa) / 2;
        if (f(wj))
            ac = wj;
        else
            wa = wj;
    }
    cout << ac << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, K;
    cin >> N >> K;
    vll A(N);
    rep(i, N) cin >> A[i];

    vint Kbit;
    vvint Abit(N);
    int mx = 60;

    {
        ll t = K;
        rep(i, mx) {
            Kbit.push_back(t % 2);
            t /= 2;
        }
        reverse(all(Kbit));

        rep(i, N) {
            ll a = A[i];
            rep(j, mx) {
                Abit[i].push_back(a % 2);
                a /= 2;
            }
            reverse(all(Abit[i]));
        }
    }

    vector dp(mx + 1, vll(2));
    rep2(i, 1, mx + 1) {
        int t = Kbit[i - 1];
        ll cnt = 0;
        rep(j, N) {
            cnt += Abit[j][i - 1];
        }

        rep(d, 2) {
            if (d < t) {
                chmax(dp[i][1], dp[i - 1][0] * 2 + cnt);
            }
            if (d == t) {
                if (d == 0)
                    chmax(dp[i][0], dp[i - 1][0] * 2 + cnt);
                else
                    chmax(dp[i][0], dp[i - 1][0] * 2 + N - cnt);
            }
            if (dp[i - 1][1]) {
                chmax(dp[i][1], dp[i - 1][1] * 2 + max(N - cnt, cnt));
            }
        }
    }

    cout << max(dp[mx][0], dp[mx][1]) << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int m = 60;

    auto f = [&](ll x) -> vint {
        vint v;
        rep(i, m) {
            v.push_back(x % 2);
            x /= 2;
        }
        reverse(all(v));
        return v;
    };

    ll N, K;
    cin >> N >> K;
    vll A(N);
    rep(i, N) cin >> A[i];

    vint kbit = f(K);
    vvint abits(N);
    rep(i, N) {
        abits[i] = f(A[i]);
    }

    // dp[is_less]
    vll dp(2, -1);
    dp[0] = 0;

    rep(i, m) {
        int t = kbit[i];
        vll dpn(2, -1);

        rep(d, 2) rep(is_less, 2) {
            if (!is_less && d > t) continue;  // K 超える数は NG
            if (dp[is_less] == -1) continue;  // 未到達な状態からの遷移は NG
            int is_less_n = is_less || d < t;

            ll cnt = 0;
            for (vint& a : abits) {
                cnt += a[i] ^ d;
            }

            chmax(dpn[is_less_n], dp[is_less] * 2 + cnt);
        }

        swap(dp, dpn);
    }

    cout << max(dp[0], dp[1]) << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string A, B;
    cin >> A >> B;

    auto cal = [](string S) -> ll {
        int N = S.size();
        vector dp(N + 1, vector(2, vector(2, vll(2))));
        dp[0][0][0][0] = 1;

        rep2(i, 1, N + 1) {
            int t = S[i - 1] - '0';
            rep(d, 10) {
                bool has_four = d == 4;
                bool has_nine = d == 9;
                if (d < t) {
                    rep(fr, 2) rep(ni, 2) {
                        dp[i][1][has_four || fr][has_nine || ni] += dp[i - 1][0][fr][ni];
                    }
                }
                if (t == d) {
                    rep(fr, 2) rep(ni, 2) {
                        dp[i][0][has_four || fr][has_nine || ni] += dp[i - 1][0][fr][ni];
                    }
                }
                rep(fr, 2) rep(ni, 2) {
                    dp[i][1][has_four || fr][has_nine || ni] += dp[i - 1][1][fr][ni];
                }
            }
        }

        ll ret = 0;
        rep(fr, 2) rep(ni, 2) {
            if (fr == 0 && ni == 0) continue;
            ret += dp[N][1][fr][ni] + dp[N][0][fr][ni];
        }

        return ret;
    };
    // cout << cal(B) << endl;
    // cout << cal(A) << endl;

    cout << cal(B) - cal(to_string(stoll(A) - 1)) << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    auto f = [](ll X) -> ll {
        string S = to_string(X);
        int N = S.size();

        // dp[is_less][used_banned_number]
        vector dp(2, vll(2));
        dp[0][0] = 1;

        rep(i, N) {
            int t = S[i] - '0';
            vector dpn(2, vll(2));

            rep(d, 10) rep(is_less, 2) rep(used, 2) {
                if (!is_less && d > t) continue;

                int is_less_n = is_less || d < t;
                int used_n = used || d == 4 || d == 9;
                dpn[is_less_n][used_n] += dp[is_less][used];
            }

            swap(dp, dpn);
        }

        return dp[0][1] + dp[1][1];
    };

    ll A, B;
    cin >> A >> B;

    cout << f(B) - f(A - 1) << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string N;
    ll K;
    cin >> N >> K;

    int M = N.size();
    vector dp(M + 1, vector(2, vll(K + 2)));
    dp[0][0][0] = 1;
    rep2(i, 1, M + 1) {
        int t = N[i - 1] - '0';
        rep(d, 10) {
            int is_not_zero = d != 0;
            rep(c, 4) {
                int nxc = min(c + is_not_zero, K + 1);
                if (d < t) {
                    dp[i][1][nxc] += dp[i - 1][0][c];
                }
                if (d == t) {
                    dp[i][0][nxc] += dp[i - 1][0][c];
                }
                dp[i][1][nxc] += dp[i - 1][1][c];
            }
        }
    }

    ll ans = dp[M][1][K] + dp[M][0][K];
    cout << ans << endl;
}