ソースコード
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<pair<ll,ll> > vp;
const ll mod=1e9+7;
ll n;
vp p,q;
vl b,c,d;
set<ll> st;
void f(ll l,ll r,ll x){
p.push_back({l,x});
q.push_back({r,x});
}
int main(){
ios::sync_with_stdio(0);
cin>>n;
b=vl(n);
c=vl(n+1);
for(int i=0;i<n;i++){
ll k,t;
cin>>k>>t;
if(k==-1) continue;
if(t<n) f(t,t+1,i);
else{
t-=n;
ll tmp=n-k+1,l=t/tmp*(k-1)+k,s=t/tmp*(1-k)+t%tmp;
cout<<s<<' '<<s+l<<endl;
if(s>=0) f(s,s+l,i);
else{
f(n+s,n,i);
f(0,s+l,i);
}
}
b[i]++;
}
sort(p.begin(),p.end());
sort(q.begin(),q.end());
ll ps=p.size(),qs=q.size(),pi=0,qi=0,I=0,res=1;
st.insert(-1);
for(int i=0;i<n;i++){
while(pi<ps&&p[pi].first<=i){
st.insert(p[pi].second);
pi++;
}
while(qi<qs&&q[qi].first<=i){
st.erase(q[qi].second);
qi++;
}
auto it=st.end();
it--;
c[n-*it-1]++;
}
for(int i=n-1;i>=0;i--) if(b[n-i-1]){
if(!c[i]){
cout<<-1<<endl;
return 0;
}
(res*=c[i])%=mod;
c[i]--;
}
for(int i=n;i>=0;i--) for(int j=0;j<c[i];j++) d.push_back(n-i);
for(int i=0;i<n;i++) if(!b[i]){
ll it=upper_bound(d.begin(),d.end(),i)-d.begin();
if(it<=I){
cout<<-1<<endl;
return 0;
}
(res*=it-I)%=mod;
I++;
}
cout<<res<<endl;
}