// BEGIN CUT HERE

 // END CUT HERE

 #line 5 "AvoidRoads.cpp"

 #include <cstdlib>

 #include <cctype>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 #include <string>

 #include <iostream>

 #include <sstream>

 #include <map>

 #include <set>

 #include <queue>

 #include <stack>

 #include <fstream>

 #include <numeric>

 #include <iomanip>

 #include <bitset>

 #include <list>

 #include <stdexcept>

 #include <functional>

 #include <utility>

 #include <ctime>

 using namespace std;

 typedef long long ll;

 const int mod = ;

 bool cut[mod];

 unsigned long long dp[][];

 int cv(int x1, int y1, int x2, int y2) {

     return ((((x1 *  % mod) + y1 *  % mod) + x2 * ) % mod + y2 * ) % mod;

 }

 class AvoidRoads

 {

         public:

         long long numWays(int width, int height, vector<string> bad) {

             int x1,y1,x2,y2;

             int& n = width;

             int& m = height;

             memset(cut, , sizeof(cut));

             memset(dp, , sizeof(dp));

             for(int i = ; i < bad.size(); i++) {

                 stringstream ss;

                 ss << bad[i];

                 ss >> x1 >> y1 >> x2 >> y2;

                 cut[cv(x1,y1,x2,y2)] = ;

                 cut[cv(x2,y2,x1,y1)] = ;

             }

             dp[][] = ;

             for(int i = ; i < n; i++) {

                 if(!cut[cv(i,,i+,)]) dp[i+][] = dp[i][];

                 else break;

             }

             for(int i = ; i < m; i++) {

                 if(!cut[cv(,i,,i+)]) dp[][i+] = dp[][i];

                 else break;

             }

             for(int i = ; i <= n; i++) {

                 for(int j = ; j <= m; j++) {

                     if(!cut[cv(i-,j,i,j)]) dp[i][j] += dp[i-][j];

                     if(!cut[cv(i,j-,i,j)]) dp[i][j] += dp[i][j-];

                 }

             }

             return dp[n][m];

         }

 // BEGIN CUT HERE

     public:

     void run_test(int Case) { if ((Case == -) || (Case == )) test_case_0(); if ((Case == -) || (Case == )) test_case_1(); if ((Case == -) || (Case == )) test_case_2(); if ((Case == -) || (Case == )) test_case_3(); }

     private:

     template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }

     void verify_case(int Case, const long long &Expected, const long long &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }

     void test_case_0() { int Arg0 = ; int Arg1 = ; string Arr2[] = {"0 0 0 1","6 6 5 6"}; vector <string> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[]))); long long Arg3 = 252LL; verify_case(, Arg3, numWays(Arg0, Arg1, Arg2)); }

     void test_case_1() { int Arg0 = ; int Arg1 = ; string Arr2[] = {}; vector <string> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[]))); long long Arg3 = 2LL; verify_case(, Arg3, numWays(Arg0, Arg1, Arg2)); }

     void test_case_2() { int Arg0 = ; int Arg1 = ; string Arr2[] = {}; vector <string> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[]))); long long Arg3 = 6406484391866534976LL; verify_case(, Arg3, numWays(Arg0, Arg1, Arg2)); }

     void test_case_3() { int Arg0 = ; int Arg1 = ; string Arr2[] = {"0 0 1 0", "1 2 2 2", "1 1 2 1"}; vector <string> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[]))); long long Arg3 = 0LL; verify_case(, Arg3, numWays(Arg0, Arg1, Arg2)); }

 // END CUT HERE

 };

 // BEGIN CUT HERE

 int main()

 {

         AvoidRoads ___test;

         ___test.run_test(-);

         return ;

 }

 // END CUT HERE