#635276 (C++17) No.1001 注文の多い順列

• 問題: No.1001 注文の多い順列
• ユーザー: penguinman
• 提出日時: 2021-03-28 10:52:45
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 83 ms / 2,000 ms
• コード長: 23,100 bytes
• コンパイル時間: 2,753 ms
• コンパイル使用メモリ: 238,640 KB
• 実行使用メモリ: 73,984 KB
• 最終ジャッジ日時: 2024-11-29 08:30:03
• 合計ジャッジ時間: 5,059 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	2 ms; 5,248 KB
testcase_03	AC	2 ms; 5,248 KB
testcase_04	AC	2 ms; 5,248 KB
testcase_05	AC	2 ms; 5,248 KB
testcase_06	AC	2 ms; 5,248 KB
testcase_07	AC	3 ms; 5,248 KB
testcase_08	AC	2 ms; 5,248 KB
testcase_09	AC	2 ms; 5,248 KB
testcase_10	AC	2 ms; 5,248 KB
testcase_11	AC	2 ms; 5,248 KB
testcase_12	AC	2 ms; 5,248 KB
testcase_13	AC	3 ms; 5,248 KB
testcase_14	AC	2 ms; 5,248 KB
testcase_15	AC	2 ms; 5,248 KB
testcase_16	AC	3 ms; 5,248 KB
testcase_17	AC	2 ms; 5,248 KB
testcase_18	AC	78 ms; 61,440 KB
testcase_19	AC	57 ms; 55,680 KB
testcase_20	AC	38 ms; 36,992 KB
testcase_21	AC	34 ms; 33,536 KB
testcase_22	AC	78 ms; 73,856 KB
testcase_23	AC	77 ms; 73,472 KB
testcase_24	AC	77 ms; 73,216 KB
testcase_25	AC	74 ms; 71,680 KB
testcase_26	AC	72 ms; 70,528 KB
testcase_27	AC	73 ms; 71,936 KB
testcase_28	AC	73 ms; 72,192 KB
testcase_29	AC	83 ms; 72,832 KB
testcase_30	AC	78 ms; 69,760 KB
testcase_31	AC	82 ms; 73,088 KB
testcase_32	AC	79 ms; 73,984 KB
testcase_33	AC	74 ms; 73,856 KB

ソースコード

#include<bits/stdc++.h>
//using namespace std;
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define rep(i, j, n) for(int i = int(j); i < int(n); i++)
#define REP(i, j, n) for(int i = int(j); i <= int(n); i++)
#define per(i, j, n) for(int i = int(j); int(n) <= i; i--)
#define ALL(a) (a).begin(),(a).end()
#define revALL(a) (a).rbegin(),(a).rend()
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define ln "\n"
using std::endl;
using std::cin;
using std::cout;
using ll = long long;
using lint = __int128;
using std::vector;
using std::string;
using std::upper_bound;
using std::lower_bound;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll, ll>;
using vs = vector<int>;
using vss = vector<vs>;
using pss = std::pair<int, int>;
using vl = vector<lint>;
using vll = vector<vl>;
using pll = std::pair<lint, lint>;
//
constexpr ll MOD = 1e9+7, root = 0;
//constexpr ll MOD = 998244353, root = 3;
//constexpr ll MOD = 924844033, root = 5;
//constexpr ll MOD = 1e4, root = 0;
//constexpr ll MOD = 1e5, root = 0;
//constexpr ll MOD = 1e6, root = 0;
//constexpr ll MOD = 1e7, root = 0;
constexpr ll MAX = 1e6+10;
constexpr ll inf = (1ll << 60);
constexpr lint linf = lint(inf) * inf;

//lint output
void lout(lint N, string add){
    string S;
    if(N < 0){
        S += '-';
        N = -N;
    }
    string T;
    if(N == 0) T += '0';
    while(N){
        T += N % 10 + '0';
        N /= 10;
    }
    reverse(ALL(T));
    S += T;
    cout << S << add;
}

//lint input
lint lin(){
    string S; cin >> S;
    bool flag = 0;
    if(S[0] == '-') flag = 1;
    lint ret = 0;
    rep(i, flag, S.size()) ret = ret * 10 + S[i] - '0';
    if(flag) ret *= -1;
    return ret;
}

//reversed priority_queue
template<class T>
class prique :public std::priority_queue<T, std::vector<T>, std::greater<T>> {};

//modpow
ll modpow(ll X, ll Y, ll mod){
    ll ret = 1;
    while(Y){
        if(Y & 1){
            ret *= X;
            ret %= mod;
        }
        X *= X;
        X %= mod;
        Y >>= 1;
    }
    return ret % mod;
}

//calc: ax + by = gcd(a, b)
template<typename T>
void extGCD(ll a, ll b, T &x, T &y){
    if(b == 0){
        x = 1;
        y = 0;
        return;
    }
    extGCD(b, a%b, y, x);
    /*(a-b)x + by = gcd(a,b)
    ax + b(y-x) = gcd(a,b)*/
    y -= a / b * x;
}

//calc: ax + by = c
template<typename T>
bool solve_equation(ll a, ll b, ll c, T &x, T &y){
    ll d = std::__gcd(a, b);
    if(c % d) return false;
    extGCD(a, b, x, y);
    ll e = a * b / d;
    x %= e;
    y %= e;
    x = (lint)x * (c/d) % e;
    y = (lint)y * (c/d) % e;
    return true;
}

//segment_tree, 1-indexed
template<typename T>
struct segment_tree{
    ll N;
    T INF;
    vector<T> node;
    segment_tree(vector<T> &X, T INF_):INF(INF_){
        N = 1;
        while(N < X.size()) N <<= 1;
        node.resize(2*N, INF);
        rep(i, 0, X.size()) node[N+i] = X[i];
        per(i, N-1, 0) node[i] = compare(node[i*2], node[i*2+1]);
    }
    T compare(T A, T B){
        return std::max(A, B);
    }
    //for max_right, min_left
    //compare をいじった時にはこちらも変えた方がよい
    bool is_lower(T A, T B){
        return A < B;
    }
    //isAdd == true: add
    //isAdd == false: update
    void update(ll index, T val, bool isAdd){
        index += N;
        if(isAdd) node[index] += val;
        else node[index] = val;
        while(index > 0){
            index >>= 1;
            node[index] = compare(node[index*2], node[index*2+1]);
        }
    }
    T calc(ll left, ll right){
        T ret = INF;
        left += N;
        right += N;
        while(left < right){
            if(left & 1) ret = compare(node[left++], ret);
            if(right & 1) ret = compare(node[--right], ret);
            left >>= 1;
            right >>= 1;
        }
        return ret;
    }
    //[left, inf)
    ll min_left(ll left, T val, ll now = 1, ll l = 0, ll r = -1){
        if(r < 0) r = N;
        if(is_lower(node[now], val) || r<=left) return r;
        if(N <= now) return l;
        ll vl = min_left(left, val, now*2, l, (l+r)/2);
        if(vl == (l+r)/2) return min_left(left, val, now*2+1, (l+r)/2, r);
        return vl;
    }
    //(-inf, right]
    //内部では (-inf, right+1)
    ll max_right(ll right, T val, ll now = 1, ll l = 0, ll r = -1){
        if(r < 0) r = N, right++;
        if(is_lower(node[now], val) || right<=l) return l-1;
        if(N <= now) return l;
        ll vr = max_right(right, val, now*2+1, (l+r)/2, r);
        if(vr == (l+r)/2-1) return max_right(right, val, now*2, l, (l+r)/2);
        return vr;
    }
};

//lazy_segment_tree
template<typename T>
struct lazy_segment_tree{
    int N, height;
    vector<T> node, lazy;
    T valINF, lazyINF;
    lazy_segment_tree(vector<T> X, T valINF_, T lazyINF_) : valINF(valINF_), lazyINF(lazyINF_){
        N = 1, height = 0;
        while(N < X.size()) N <<= 1, height++;
        node.resize(2*N, valINF);
        lazy.resize(2*N, lazyINF);
        rep(i, 0, X.size()) node[i+N] = X[i];
        per(i, N-1, 0) node[i] = compare(node[i*2], node[i*2+1]);
    }
    void add(ll left, ll right, T val){
        ll l = left+N, r = right+N;
        ll L = l, R = r;
        per(i, height, 0){
            eval(l >> i);
            eval(r >> i);
        }
        while(l < r){
            if(l & 1){
                addition(lazy[l], val);
                l++;
            }
            if(r & 1){
                r--;
                addition(lazy[r], val);
            }
            l >>= 1;
            r >>= 1;
        }
        while(L){
            if(lazy[L]==lazyINF && L<N){
                eval(L*2);
                eval(L*2+1);
                node[L] = compare(node[L*2], node[L*2+1]);
            }
            if(lazy[R]==lazyINF && R<N){
                eval(R*2);
                eval(R*2+1);
                node[R] = compare(node[R*2], node[R*2+1]);
            }
            L >>= 1;
            R >>= 1;
        }
    }
    T calc(ll left, ll right){
        ll l = left+N, r = right+N;
        per(i, height, 0){
            eval(l >> i);
            eval(r >> i);
        }
        T ret = valINF;
        while(l < r){
            if(l & 1){
                eval(l);
                ret = compare(node[l], ret);
                l++;
            }
            if(r & 1){
                r--;
                eval(r);
                ret = compare(node[r], ret);
            }
            l >>= 1;
            r >>= 1;
        }
        return ret;
    }
    //[left, inf)
    ll min_left(ll left, T val, ll now = 1, ll l = 0, ll r = -1){
        if(r < 0) r = N;
        eval(now);
        if(is_lower(node[now], val) || r<=left) return r;
        if(N <= now) return l;
        ll vl = min_left(left, val, now*2, l, (l+r)/2);
        if(vl == (l+r)/2) return min_left(left, val, now*2+1, (l+r)/2, r);
        return vl;
    }
    //(-inf, right]
    //内部では (-inf, right+1)
    ll max_right(ll right, T val, ll now = 1, ll l = 0, ll r = -1){
        if(r < 0) r = N, right++;
        eval(now);
        if(is_lower(node[now], val) || right<=l) return l-1;
        if(N <= now) return l;
        ll vr = max_right(right, val, now*2+1, (l+r)/2, r);
        if(vr == (l+r)/2-1) return max_right(right, val, now*2, l, (l+r)/2);
        return vr;
    }

    private:

    T compare(T A, T B){
        return std::max(A, B);
    }
    //for max_right, min_left
    //compare をいじった時にはこちらも変えた方がよい
    bool is_lower(T A, T B){
        return A < B;
    }
    void addition(T &A, T B){
        //addition : 
        A += B;
        //update : A = B;
    }
    void eval(int now){
        if(lazy[now] == lazyINF) return;
        if(now < N){
            addition(lazy[now*2], lazy[now]);
            addition(lazy[now*2+1], lazy[now]);
        }
        addition(node[now], lazy[now]);
        lazy[now] = lazyINF;
    }
};

struct Union_Find{
    ll N;
    vi par;
    vi siz;
    Union_Find(int n):N(n){
        par.resize(N);
        siz.resize(N,1);
        rep(i,0,N) par[i]=i;
    }
    ll root(ll X){
        if(par[X]==X) return X;
        return par[X]=root(par[X]);
    }
    bool same(ll X,ll Y){
        return root(X)==root(Y);
    }
    void unite(ll X,ll Y){
        X=root(X);
        Y=root(Y);
        if(X==Y) return;
        if(siz[Y]<siz[X]) std::swap(X,Y);
        par[X]=Y;
        siz[Y]+=siz[X];
        siz[X]=0;
    }
    ll size(ll X){
        return siz[root(X)];
    }
};
struct Directed_Gragh{
    ll N,M;
    vii edge;
    Directed_Gragh(vii e):edge(e){
        N=edge.size();
        rep(i,0,N) M+=edge[i].size();
    }
    vi sort(){
        vi ret;
        vi cnt(N);
        rep(i,0,N){
            for(auto p:edge[i]) cnt[p]++;
        }
        std::queue<ll> que;
        rep(i,0,N){
            if(cnt[i]==0) que.push(i);
        }
        while(!que.empty()){
            ll now=que.front(); que.pop();
            ret.pb(now);
            for(auto next:edge[now]){
                cnt[next]--;
                if(cnt[next]==0) que.push(next);
            }
        }
        return ret;
    }
    vii SCC(){
        vii revedge(N),ver;
        vi ind(N);
        rep(i,0,N){
            for(auto p:edge[i]) revedge[p].pb(i);
        }
        vi num(N,-1),po(N);
        vector<bool> seen(N);
        ll cnt=0;
        rep(i,0,N){
            if(num[i]==-1){
                dfs(i,num,cnt);
            }
        }
        rep(i,0,N) po[num[i]]=i;
        per(i,N-1,0){
            ll X=po[i];
            if(!seen[X]){
                std::queue<ll> que;
                vi v;
                que.push(X);
                seen[X]=1;
                while(!que.empty()){
                    ll now=que.front(); que.pop();
                    v.pb(now);
                    ind[now]=ver.size();
                    for(auto p:revedge[now]){
                        if(!seen[p]){
                            seen[p]=1;
                            que.push(p);
                        }
                    }
                }
                ver.pb(v);
            }
        }
        return ver;
    }
    void dfs(ll now,vi &num,ll &cnt){
        num[now]=0;
        for(auto next:edge[now]){
            if(num[next]==-1){
                dfs(next,num,cnt);
            }
        }
        num[now]=cnt++;
    }
};
struct Tree{
    int N;
    vii dp;
    vi par;
    vi dist;
    vi subtree;
    vii edge;
    Tree(vii E):edge(E){
        N=edge.size();
        dp.resize(N);
        par.resize(N);
        dist.resize(N,-1);
        for(int i=0;i<N;i++) dp[i].resize(20);
        dist[0]=dp[0][0]=0;
        std::queue<int> que;
        que.push(0);
        while(!que.empty()){
            int now=que.front(); que.pop();
            for(int i=0;i<edge[now].size();i++){
                int next=edge[now][i];
                if(dist[next]==-1){
                    dist[next]=dist[now]+1;
                    que.push(next);
                    par[next]=now;
                    dp[next][0]=now;
                }
            }
        }
        for(int i=1;i<20;i++){
            for(int j=0;j<N;j++) dp[j][i]=dp[dp[j][i-1]][i-1];
        }
    }
    int LCA(int X,int Y){
        if(dist[X]<dist[Y]) std::swap(X,Y);
        {
            int Z=dist[X]-dist[Y];
            int i=0;
            while(Z){
                if(Z&1) X=dp[X][i];
                i++;
                Z>>=1;
            }
        }
        if(X==Y) return X;
        for(int i=19;i>=0;i--){
            if(dp[X][i]!=dp[Y][i]){
                X=dp[X][i];
                Y=dp[Y][i];
            }
        }
        return dp[X][0];
    }
    void Subtree(){
        subtree.resize(N,-1);
        dfs(0);
    }
    void dfs(ll now){
        subtree[now]=1;
        for(auto next:edge[now]){
            if(subtree[next]==-1){
                dfs(next);
                subtree[now]+=subtree[next];
            }
        }
    }
};
template<typename T>
struct max_flow{
    struct Edge{
        int to;
        T cap;
        int rev;
    };
    int N;
    vector<vector<Edge>> edge;
    vector<int> dist,itr;
    max_flow(vii e,vii w){
        N=e.size();
        edge.resize(N);
        rep(i,0,N){
            rep(j,0,e[i].size()){
                edge[i].pb((Edge){(int)e[i][j],(T)w[i][j],(int)edge[e[i][j]].size()});
                edge[e[i][j]].pb((Edge){i,0,(int)edge[i].size()-1});
            }
        }
    }
    void add_edge(int from,int to,T cap){
        edge[from].pb((Edge){to,cap,(int)edge[to].size()});
        edge[to].pb((Edge){from,0,(int)edge[from].size()-1});
    }
    void bfs(int s){
        dist.assign(N,-1);
        std::queue<int> que;
        dist[s]=0;
        que.push(s);
        while(!que.empty()){
            int now=que.front(); que.pop();
            for(auto p:edge[now]){
                int next=p.to;
                if(p.cap>0&&dist[next]<0){
                    dist[next]=dist[now]+1;
                    que.push(next);
                }
            }
        }
    }
    T dfs(int now,int t,T f){
        if(now==t) return f;
        for(;itr[now]<edge[now].size();itr[now]++){
            Edge& p=edge[now][itr[now]];
            if(p.cap>0&&dist[now]<dist[p.to]){
                T mem=dfs(p.to,t,std::min(f,p.cap));
                if(mem>0){
                    p.cap-=mem;
                    edge[p.to][p.rev].cap+=mem;
                    return mem;
                }
            }
        }
        return 0;
    }
    T Query(int s,int t){
        T ret=0;
        while(1){
            bfs(s);
            if(dist[t]<0) break;
            itr.assign(N,0);
            while(1){
                int mem=dfs(s,t,(1<<30));
                if(mem<=0) break;
                ret+=mem;
            }
        }
        return ret;
    }
};
struct min_cost_flow{
    struct Edge{
        int to,cap,rev;
        ll cost;
    };
    int N;
    vector<vector<Edge>> edge;
    vector<ll> dist,h;
    void add_edge(int from,int to,int cap,ll cost){
        edge[from].pb((Edge){to,cap,(int)edge[to].size(),cost});
        edge[to].pb((Edge){from,0,(int)edge[from].size()-1,-cost});
    }
    min_cost_flow(vii e,vii m,vii w){
        N=e.size();
        edge.resize(N);
        rep(i,0,N){
            rep(j,0,e[i].size()){
                add_edge(i,e[i][j],m[i][j],w[i][j]);
            }
        }
    }
    void potential(){
        h.assign(N,0);
        vector<vector<int>> edge2(N);
        vii weight(N);
        vector<int> cnt(N);
        rep(i,0,N){
            for(auto e:edge[i]){
                if(e.cap>0&&e.cost<0){
                    edge2[i].pb(e.to);
                    weight[i].pb(-e.cost);
                    cnt[e.to]++;
                }
            }
        }
        std::queue<ll> que;
        rep(i,0,N){
            if(cnt[i]==0) que.push(i);
        }
        vector<int> ver;
        while(!que.empty()){
            int now=que.front(); que.pop();
            ver.pb(now);
            for(auto next:edge2[now]){
                cnt[next]--;
                if(cnt[next]==0) que.push(next);
            }
        }
        per(i,N-1,0){
            rep(j,0,edge2[ver[i]].size()){
                int next=edge2[ver[i]][j];
                h[ver[i]]=std::max(h[ver[i]],h[next]+weight[ver[i]][j]);
            }
        }
    }
    ll Query(int s,int t,int f){
        ll ret=0;
        potential();
        while(f){
            vi dist(N,inf);
            vector<int> memv(N),meme(N);
            dist[s]=0;
            prique<std::pair<ll,int>> que;
            que.push(mp(0,s));
            while(!que.empty()){
                auto now=que.top().second; 
                if(dist[now]<que.top().first){
                    que.pop();
                    continue;
                }
                que.pop();
                rep(i,0,edge[now].size()){
                    auto e=edge[now][i];
                    auto next=e.to;
                    if(e.cap>0&&dist[next]>dist[now]+h[now]-h[next]+e.cost){
                        dist[next]=dist[now]+h[now]-h[next]+e.cost;
                        memv[next]=now;
                        meme[next]=i;
                        que.push(mp(dist[next],next));
                    }
                }
            }
            if(dist[t]==inf) return -1;
            int now=t,max=f;
            while(now!=s){
                auto& e=edge[memv[now]][meme[now]];
                max=std::min(max,e.cap);
                now=memv[now];
            }
            f-=max;
            now=t;
            while(now!=s){
                auto& e=edge[memv[now]][meme[now]];
                e.cap-=max;
                auto& e2=edge[e.to][e.rev];
                e2.cap+=max;
                now=memv[now];
            }
            rep(i,0,N) h[i]+=dist[i];
            ret+=h[t]*max;
        }
        return ret;
    }
};
struct Fast_Fourier_Transform{
    void dft(vector<std::complex<double>> &func,int inverse){
        int siz=func.size();
        if(siz==1) return;
        vector<std::complex<double>> left,right;
        rep(i,0,siz/2){
            left.pb(func[i*2]);
            right.pb(func[i*2+1]);
        }
        dft(left,inverse);
        dft(right,inverse);
        std::complex<double> now=1,zeta=std::polar(1.0,inverse*2.0*acos(-1)/siz);
        rep(i,0,siz){
            func[i]=left[i%(siz/2)]+now*right[i%(siz/2)];
            now*=zeta;
        }
    }
    template<typename T>
    vector<double> multiply(vector<T> f,vector<T> g){
        vector<std::complex<double>> nf,ng;
        int siz=1;
        while(siz<f.size()+g.size()) siz<<=1;
        nf.resize(siz);
        ng.resize(siz);
        rep(i,0,f.size()) nf[i]=f[i];
        rep(i,0,g.size()) ng[i]=g[i];
        dft(nf,1);
        dft(ng,1);
        rep(i,0,siz) nf[i]*=ng[i];
        dft(nf,-1);
        vector<double> ret(siz);
        rep(i,0,siz) ret[i]=nf[i].real()/siz;
        return ret;
    }
};
struct Numver_Theoretic_Transform{
    vii mem;
    Numver_Theoretic_Transform(void){
        mem.resize(25,vi(2));
        rep(i,0,25){
            mem[i][1]=modpow(root,MOD-1-(MOD-1)/(1<<i),MOD);
            mem[i][0]=modpow(root,(MOD-1)/(1<<i),MOD);
        }
    }
    void dft(vi &func,bool inverse,ll cnt){
        int siz=func.size();
        if(siz==1) return;
        vi left,right;
        rep(i,0,siz/2){
            left.pb(func[i*2]);
            right.pb(func[i*2+1]);
        }
        dft(left,inverse,cnt-1);
        dft(right,inverse,cnt-1);
        ll now=1;
        ll zeta=mem[cnt][inverse];
        rep(i,0,siz){
            func[i]=(left[i%(siz/2)]+now*right[i%(siz/2)])%MOD;
            now*=zeta;
            now%=MOD;
        }
    }
    vi multiply(vi f,vi g){
        ll cnt=0;
        vi nf,ng;
        int siz=1;
        while(siz<f.size()+g.size()){
            cnt++;
            siz<<=1;
        }
        nf.resize(siz);
        ng.resize(siz);
        rep(i,0,f.size()) nf[i]=f[i];
        rep(i,0,g.size()) ng[i]=g[i];
        dft(nf,0,cnt);
        dft(ng,0,cnt);
        rep(i,0,siz){
            nf[i]*=ng[i];
            nf[i]%=MOD;
        }
        dft(nf,1,cnt);
        vi ret(siz);
        ll div=modpow(siz,MOD-2,MOD);
        rep(i,0,siz) ret[i]=nf[i]*div%MOD;
        return ret;
    }
};
struct Trie{
    int let;
    char lower;
    vector<int> cnt;
    vector<vector<int>> next;
    Trie(int element,char low):let(element),lower(low){
        cnt.resize(1);
        next.pb(vector<int>(let,-1));
    }
    void insert(string S){
        int now=0;
        for(auto s:S){
            int X=s-lower;
            if(next[now][X]==-1){
                next[now][X]=cnt.size();
                cnt.pb(0);
                next.pb(vector<int>(lower,-1));
            }
            now=next[now][X];
        }
        cnt[now]++;
    }
    int get(string S){
        int now=0;
        for(auto s:S){
            int X=s-lower;
            if(next[now][X]==-1) return 0;
            now=next[now][X];
        }
        return cnt[now];
    }
};
template<typename T>
struct tancomp{
    int place(std::pair<T,T> p){
        if(p.first<=0&&p.second<0) return 0;
        if(p.first>0&&p.second<=0) return 1;
        if(p.first==0&&p.second==0) return 2;
        if(p.first>=0&&p.second>0) return 3;
        return 4;
    }
    bool operator()(const std::pair<T,T> &l,const std::pair<T,T> &r){
        if(place(l)!=place(r)) return place(l)<place(r);
        //l.second/l.first<r.second/r.first
        return l.second*r.first<l.first*r.second;
    }
};
template<typename T>
vector<std::pair<T,T>> Declination_sort(ll N,vector<T> X,vector<T> Y){
    vector<std::pair<T,T>> ret(N);
    rep(i,0,N){
        ret[i]=(mp(X[i],Y[i]));
    }
    sort(ALL(ret),tancomp<T>());
    return ret;
}
vi get_bases(vi A,ll max_digit){
    int now=0;
    int N=A.size();
    per(i,max_digit,0){
        rep(j,now,N){
            if(A[j]&(1ll<<i)){
                std::swap(A[j],A[now]);
                break;
            }
        }
        if(now<N&&A[now]&(1ll<<i)){
            rep(j,0,N){
                if(j!=now&&A[j]&(1ll<<i)) A[j]^=A[now];
            }
            now++;
        }
    }
    vi bases;
    rep(i,0,now) bases.pb(A[i]);
    return bases;
}
vi fac,finv,inv;
void COMinit() {
    fac.resize(MAX);
    finv.resize(MAX);
    inv.resize(MAX);
    fac[0]=fac[1]=1;
    inv[1]=1;
    finv[0]=finv[1]=1;
    rep(i,2,MAX){
        fac[i]=fac[i-1]*i%MOD;
        inv[i]=MOD-MOD/i*inv[MOD%i]%MOD;
        finv[i]=finv[i-1]*inv[i]%MOD;
    }
}
ll COM(ll n,ll r){
    if(n<r||n<0||r<0) return 0;
    return fac[n]*finv[r]%MOD*finv[n-r]%MOD;
}
void comp(vi &A){
    std::map<ll,ll> memo;
    rep(i,0,A.size()) memo[A[i]]=0;
    ll cnt=0;
    for(auto &p:memo) p.second=cnt++;
    rep(i,0,A.size()) A[i]=memo[A[i]];
}
void dec(std::map<ll,ll> &mem,ll X){
    mem[X]--;
    if(mem[X]==0) mem.erase(X);
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::random_device rnd;
    std::mt19937 mt(rnd());
    ll N; cin >> N;
    vii mem(N,vi(2));
    rep(i,0,N){
        ll t, X; cin >> t >> X;
        mem[X-1][t]++;
    }
    //i 番目、t_i = 0 に j 個
    vii dp(N+1,vi(N+1));
    dp[0][0] = 1;
    vi cnt(2);
    rep(i,0,N){
        cnt[1] += mem[i][1];
        REP(j,0,i){
            //1 個ストックを増やす
            dp[i+1][j+1] += dp[i][j];
            dp[i+1][j+1] %= MOD;
            //ストックを使わない
            //j+cnt[0] がこれまでの 0 の使用数
            //つまり i-j-cnt[0] がこれまでで使った 1 の数
            if(j+cnt[0] <= i) dp[i+1][j] += dp[i][j]*std::max(0ll,cnt[1]-(i-j-cnt[0]));
            dp[i+1][j] %= MOD;
        }
        cnt[0] += mem[i][0];
        rep(j,0,mem[i][0]){
            //その後削る
            REP(k,0,i){
                dp[i+1][k] = dp[i+1][k+1]*(k+1)%MOD;
            }
        }
    }
    cout << dp[N][0] << ln;
}