ARC 124

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;
}