#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair P; const ll MOD=1e9+7; ll solve(vector l, vector r){ int m=l.size(); vector v(2*m); for(int i=0; i=r[i]) return 0; v[2*i]=l[i], v[2*i+1]=r[i]; } sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); int n=v.size(); for(int i=0; ivoid{ if(k==m){ int cnt[10]={}; for(int i=0; i=MOD) ret-=MOD; return; } for(int i=l[k]; i>a[i]>>b[i]; ll ans=0; for(int i=2; i<=20000; i++){ vector l(3), r(3); for(int j=0; j<3; j++){ l[j]=max(i, a[2*j+1]); r[j]=b[2*j+1]+1; } ll s=solve(l, r); for(int j=0; j<3; j++){ l[j]=max(i+1, a[2*j+1]); r[j]=b[2*j+1]+1; } s=(s-solve(l, r)+MOD)%MOD; if(s==0) continue; l.resize(4); r.resize(4); for(int j=0; j<4; j++){ l[j]=a[2*j]; r[j]=min(i, b[2*j]+1); } (s*=solve(l, r))%=MOD; (ans+=s)%=MOD; } for(int i=2; i<=20000; i++){ vector l(4), r(4); for(int j=0; j<4; j++){ l[j]=max(i, a[2*j]); r[j]=b[2*j]+1; } ll s=solve(l, r); for(int j=0; j<4; j++){ l[j]=max(i+1, a[2*j]); r[j]=b[2*j]+1; } s=(s-solve(l, r)+MOD)%MOD; if(s==0) continue; l.resize(3); r.resize(3); for(int j=0; j<3; j++){ l[j]=a[2*j+1]; r[j]=min(i, b[2*j+1]+1); } (s*=solve(l, r))%=MOD; (ans+=s)%=MOD; } cout<