#include bool Mbe; using namespace std; #define il inline typedef long long ll; typedef unsigned long long ull; typedef double db; typedef pair pii; typedef array ai2; il void ins(ai2&c, int d) {c[c[0]!=0]=d; } // typedef pair pli; // typedef pair pll; #define fi first #define se second typedef vector vi; template il bool cmax(t1&x, const t1&y) {return x il bool cmin(t1&x, const t1&y) {return y>=1);; return re;} il ll inv(ll a, ll b=mod-2, ll re=1) {for (a%=mod; b; b&1?(re*=a)%=mod,1:0, (a*=a)%=mod, b>>=1);; return re;} const int FN=3000; int fac[FN+3], ifac[FN+3]; il void MathInit(int n=FN) { fac[0]=ifac[0]=1; for (int i=1; i<=n; ++i) fac[i]=int((ll)fac[i-1]*i%mod), ifac[i]=int((ll)fac[i]*ifac[i-1]%mod); for (int i=n, c=(int)inv(ifac[n]); i>=1; --i) ifac[i]=int((ll)c*ifac[i-1]%mod), c=int((ll)c*fac[i]%mod); } il ll inv(int x) {return (ll)ifac[x]*fac[x-1]%mod; } il ll C(int b, int a) {return b>n, MathInit(n); for (int i=1; i<=n; ++i) cin>>p[i].se >> p[i].fi, p[i].fi-=p[i].se, tot[p[i].se]++;; //, fac[i]=int((ll)fac[i-1]*i%mod); sort(p+1, p+1+n), dp[0][0]=1; for (int i=1,o=1,fr0=0; i<=n; ++i,o^=1) { for (int j=0; j<=i; ++j) dp[o][j]=0; for (int j=0; j<=i; ++j) if (dp[o^1][j]) { if (p[i].se) { (dp[o][j+1]+=dp[o^1][j]*(p[i].fi-(fr0+j)))%=mod; (dp[o][ j ]+=dp[o^1][j])%=mod; } else { (dp[o][j]+=dp[o^1][j]*(p[i].fi-(fr0+j)))%=mod; } } fr0+=(p[i].se==0); } ll ans=0; for (int j=0; j<=tot[1]; ++j) (ans+=(j&1?-1:+1)*dp[n&1][j]*((ll)fac[n-(tot[0]+j)]))%=mod; // *ifac[]%mod cout << Mod(ans) << '\n'; } bool Men; int main() { // g++ L26_1A.cpp -o L26_1A.exe -O2 -std=c++14 -Wall -Wextra -Wconversion -Wshadow -DMYFRE // g++ Yukicoder1001.cpp -o Yukicoder1001.exe -O2 -std=c++14 -Wall -Wextra -Wconversion -Wshadow -DMYFRE ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); #ifdef MYFRE cerr << "L26_1A Yukicoder1001" << endl; cerr << "L26_1A Yukicoder1001" << endl; cerr << "L26_1A Yukicoder1001" << endl; cerr << "M: " << db(&Mbe-&Men)/1024/1024 << endl; freopen("0.in", "r", stdin), freopen("0.out", "w", stdout); #else // freopen("Yukicoder1001.in", "r", stdin), freopen("Yukicoder1001.out", "w", stdout); #endif // freopen() // MathInit(); solve();//>>testid // int testid,testtt; cin>>testid>>testtt; for (int ti=1; ti<=testtt; ++ti) solve(); #ifdef MYFRE cerr << "T: " << (db)clock()/CLOCKS_PER_SEC << endl; /* copy Yukicoder1001\Yukicoder10011.in Yukicoder1001.in Yes Yukicoder1001.exe fc /W Yukicoder1001.out Yukicoder1001\Yukicoder10011.ans */ #endif }