#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
using namespace std;
typedef long long LL;
typedef long double LD;
typedef complex<LD> CMP;
static const unsigned MODVAL = 1000000007;
class WolfInZooDivOne { public:
int count(int N, vector <string> L_, vector <string> R_)
{
vector<int> L, R;
{
stringstream sin(accumulate(L_.begin(), L_.end(), string()));
for(int s; sin>>s;) L.push_back(s);
}
{
stringstream sin(accumulate(R_.begin(), R_.end(), string()));
for(int s; sin>>s;) R.push_back(s+1);
}
set< pair<int,int> > LR;
for(int i=0; i<L.size(); ++i)
LR.insert(make_pair(L[i], R[i]));
vector< pair<int,int> > LR_imp;
for(set< pair<int,int> >::iterator it=LR.begin(); it!=LR.end(); ++it) {
bool important = true;
for(set< pair<int,int> >::iterator kt=LR.begin(); kt!=LR.end(); ++kt)
if(it != kt && kt->first<=it->first && it->second<=kt->second)
important = false;
if(important)
LR_imp.push_back(*it);
}
return solve(N, LR_imp);
}
int solve(int N, const vector< pair<int,int> >& LR)
{
memo = vector<vector<vector<int> > >(N,
vector<vector<int> >(LR.size()+1, vector<int>(LR.size()+1, -1)));
return rec(0, N, LR, 0, 0, 0, 0);
}
vector<vector<vector<int> > > memo;
int rec(int i, const int N, const vector< pair<int,int> >& LR, int end_of_past, int end_of_two, int end_of_one,
int end_of_zero)
{
if(i == N)
return 1;
int& me = memo[i][end_of_two][end_of_one];
if(me != -1)
return me;
int ez = end_of_zero;
while(ez<LR.size() && LR[ez].first<=i)
++ez;
int ep = end_of_past;
while(ep<ez && LR[ep].second<=i)
++ep;
// do not place wolf at i.
int total = rec(i+1, N, LR, ep, max(ep,end_of_two), max(ep,end_of_one), ez);
// place wolf at i.
if(ep >= end_of_two) {
int e1 = max(ep, end_of_one);
int e2 = max(ep, end_of_two);
while(e2<e1 && i<LR[e2].second)
++e2;
while(e1<ez && i<LR[e1].second)
++e1;
total += rec(i+1, N, LR, ep, e2, e1, ez);
}
return me = (total % MODVAL);
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, WolfInZooDivOne().count(N, L, R));}
int main(){
CASE(0)
int N = 5;
string L_[] = {"0"};
vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_));
string R_[] = {"4"};
vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_));
int _ = 16;
END
CASE(1)
int N = 5;
string L_[] = {"0 1"};
vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_));
string R_[] = {"2 4"};
vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_));
int _ = 21;
END
CASE(2)
int N = 10;
string L_[] = {"0 4 2 7"};
vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_));
string R_[] = {"3 9 5 9"};
vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_));
int _ = 225;
END
CASE(3)
int N = 100;
string L_[] = {"0 2 2 7 10 1","3 16 22 30 33 38"," 42 44 49 51 57 60 62"," 65 69 72 74 77 7","8 81 84 88 91 93 96"};
vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_));
string R_[] = {"41 5 13 22 12 13 ","33 41 80 47 40 ","4","8 96 57 66 ","80 60 71 79"," 70 77 ","99"," 83 85 93 88 89 97 97 98"};
vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_));
int _ = 6419882;
END
/*
CASE(4)
int N = ;
string L_[] = ;
vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_));
string R_[] = ;
vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_));
int _ = ;
END
CASE(5)
int N = ;
string L_[] = ;
vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_));
string R_[] = ;
vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_));
int _ = ;
END
*/
}
// END CUT HERE