ABC 448

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

    ll n, x;
    cin >> n >> x;
    rep(i, n) {
        ll a;
        cin >> a;
        if (a < x) {
            cout << 1 << endl;
            x = a;
        } else {
            cout << 0 << endl;
        }
    }
}

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

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

    vvll food(M);
    rep(i, N) {
        ll a, b;
        cin >> a >> b;
        a--;
        food[a].pb(b);
    }

    ll ans = 0;
    rep(i, M) {
        ll rem = C[i];
        for (auto x : food[i]) {
            ll d = min(rem, x);
            ans += d;
            rem -= d;
        }
    }
    cout << ans << endl;
}

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

    ll N, Q;
    cin >> N >> Q;

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

    multiset<ll> ma;
    for (ll a : A) ma.insert(a);

    while (Q--) {
        ll K;
        cin >> K;
        vll B(K);
        rep(i, K) {
            cin >> B[i];
            B[i]--;
        }

        for (ll b : B) {
            auto it = ma.lower_bound(A[b]);
            ma.erase(it);
        }

        cout << *ma.begin() << endl;

        for (ll b : B) {
            ma.insert(A[b]);
        }
    }
}

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

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

    vvint graph(N);
    rep(i, N - 1) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    vint ans(N);
    multiset<ll> S;

    auto dfs = [&](auto dfs, int now, int p, int ok) -> void {
        if (S.count(A[now])) {
            ok = 1;
        }
        if (ok) {
            ans[now] = 1;
        }

        S.insert(A[now]);

        for (int nx : graph[now]) {
            if (nx == p) continue;
            dfs(dfs, nx, now, ok);
        }
        auto it = S.lower_bound(A[now]);
        S.erase(it);
    };

    dfs(dfs, 0, -1, 0);

    for (int x : ans) yesno(x);
}

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

    ll K, M;
    cin >> K >> M;

    vll C(K), L(K);
    rep(i, K) cin >> C[i] >> L[i];

    auto cal = [&](ll mod) -> ll {
        modint::set_mod(mod);
        using mint = modint;

        int up = 32;
        vector<mint> d(up);

        mint ten = 10;

        // d[i]: ( 1 が 2^i 個並んだ数字 ) % M
        d[0] = 1 % mod;
        rep2(i, 1, up) {
            d[i] = d[i - 1] * ten.pow(1ll << (i - 1)) + d[i - 1];
        }

        // ( 1 が x 個並んだ数 ) % M
        auto ones = [&](ll x) -> mint {
            mint ret = 0;
            rep(i, up) {
                if (x >> i & 1) {
                    ret *= ten.pow(1ll << i);
                    ret += d[i];
                }
            }
            return ret;
        };

        mint r = 0;
        rep(i, K) {
            r *= ten.pow(L[i]);
            r += (C[i] * ones(L[i]));
        }

        return r.val();
    };

    // 10007 は素数
    ll mod = 10007;
    ll r = cal(M);
    ll n = cal(mod);

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

    mint mr = mint(r), mn = mint(n);
    cout << ((mn - mr) * mint(M).inv()).val() << endl;
}

struct Matrix {
    vvll data;
    ll MOD;

    Matrix(vvll data, ll mod) : MOD(mod) { this->data = data; }

    Matrix operator*(const Matrix& other) {
        int n = data.size();
        int m = other.data[0].size();
        int l = other.data.size();
        vvll res(n, vll(m, 0));
        rep(i, n) rep(j, m) rep(k, l) {
            res[i][j] += data[i][k] * other.data[k][j];
            res[i][j] %= MOD;
        }
        return Matrix(res, MOD);
    }

    Matrix exp(ll k) {
        int n = data.size();
        Matrix res(vvll(n, vll(n, 0)), MOD);
        rep(i, n) res.data[i][i] = 1;
        Matrix a = *this;
        while (k > 0) {
            if (k & 1)
                res = res * a;
            a = a * a;
            k >>= 1;
        }
        return res;
    }
};

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

    ll K, M;
    cin >> K >> M;

    vll C(K), L(K);
    rep(i, K) cin >> C[i] >> L[i];

    auto cal = [&](ll mod) -> ll {
        modint::set_mod(mod);
        using mint = modint;

        int up = 32;
        vector<mint> d(up);

        // ( 1 が x 個並んだ数 ) % M
        auto ones = [&](ll x) -> mint {
            Matrix v({{1}, {1}}, mod);
            Matrix mat({{10, 1}, {0, 1}}, mod);
            Matrix p = mat.exp(x - 1) * v;
            return p.data[0][0];
        };

        mint ten = 10;

        mint r = 0;
        rep(i, K) {
            r *= ten.pow(L[i]);
            r += (C[i] * ones(L[i]));
        }

        return r.val();
    };

    // 10007 は素数
    ll mod = 10007;
    ll r = cal(M);
    ll n = cal(mod);

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

    mint mr = mint(r), mn = mint(n);
    cout << ((mn - mr) * mint(M).inv()).val() << endl;
}