#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



#define SIZE 200005

struct Info{
	Info(ll arg_row1,ll arg_col1,ll arg_row2,ll arg_col2){
		row1 = arg_row1;
		col1 = arg_col1;
		row2 = arg_row2;
		col2 = arg_col2;
	}
	bool operator<(const struct Info &arg) const{

		if(row1 != arg.row1){

			return row1 < arg.row1;
		}else{

			return col1 < arg.col1;
		}
	}

	ll row1,col1,row2,col2;
};

ll H,W,K;
ll dp[1005];
ll fact[SIZE];


ll extgcd(ll a,ll b,ll &x,ll &y){
	ll d = a;
	if(b != 0){
		d = extgcd(b,a%b,y,x);
		y -= (a/b)*x;
	}else{
		x = 1;
		y = 0;
	}
	return d;
}

ll mod_pow(ll x,ll count, ll mod){

	if(count == 0)return 1;
	ll ret = mod_pow((x*x)%mod,count/2,mod);
	if(count%2 == 1){

		ret = (ret*x)%mod;
	}
	return ret;
}


ll mod_inverse(ll a,ll m){
    ll x,y;
    extgcd(a,m,x,y);
    return (m+x%m)%m;
}

ll mod_fact(ll n,ll p,ll &e){
	e = 0;
	if(n == 0)return 1;

	int res = mod_fact(n/p,p,e);
	e += n/p;

	if(n/p%2 != 0)return res*(p-fact[n%p])%p;
	return res*fact[n%p]%p;
}


ll nCm(ll n,ll m,ll p){
   if(n < m) return 0;
   ll e1,e2,e3;
   ll a1 = mod_fact(n,p,e1),a2 = mod_fact(m,p,e2),a3 = mod_fact(n-m,p,e3);
   if(e1 > e2+e3)return 0;
   return a1 * mod_inverse(a2*a3%p,p)%p;
}

void func(){

	vector<Info> V;

	ll col1,row1,col2,row2;

	for(int loop = 0; loop < K; loop++){

		scanf("%lld %lld %lld %lld",&col1,&row1,&col2,&row2);

		V.push_back(Info(row1,col1,row2,col2));
	}

	sort(V.begin(),V.end());

	ll minus,A,B;

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

		dp[i] = nCm(V[i].row1+V[i].col1-2,V[i].row1-1,MOD);

		for(int k = 0; k <= i-1; k++){
			if(V[k].col1 > V[i].col1)continue;

			A = nCm((V[i].row1-V[k].row1+V[i].col1-V[k].col1),V[i].row1-V[k].row1,MOD);
			if(V[k].col2 > V[i].col1 || V[k].row2 > V[i].row1){

				B = 0;

			}else{

				B = nCm((V[i].row1-V[k].row2+V[i].col1-V[k].col2),V[i].row1-V[k].row2,MOD);
			}

			minus = (A-B+MOD)%MOD;
			minus *= dp[k];
			minus %= MOD;

			dp[i] = (dp[i]-minus+MOD)%MOD;
		}
	}

	ll ans = nCm(H+W-2,H-1,MOD);

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

		A = nCm(H-V[i].row1+W-V[i].col1,H-V[i].row1,MOD);
		B = nCm(H-V[i].row2+W-V[i].col2,H-V[i].row2,MOD);

		minus = (A-B+MOD)%MOD;
		minus *= dp[i];
		minus %= MOD;

		ans = (ans-minus+MOD)%MOD;
	}

	printf("%lld\n",ans);
}


int main(){

	fact[0] = 1;
	for(ll i = 1; i < SIZE; i++){
		fact[i] = i*fact[i-1];
		fact[i] %= MOD;
	}

	while(true){

		scanf("%lld %lld %lld",&W,&H,&K);
		if(H == 0 && W == 0 && K == 0)break;

		func();
	}

	return 0;
}


### Prompt

Construct a CPP code solution to the problem outlined:

In 20XX, an efficient material transfer method was established for distant places, and human beings' advance into space was accelerated more and more. This transfer method was innovative in that, in principle, larger substances could be transferred when trying to transfer the substance farther. The details of the transfer method are described below.

First, the substance to be transferred is divided into particles for each unit mass at the start coordinates (1, 1). Each particle must be given a different wave energy. Wave energy is represented by a character string of arbitrary length consisting of V and H, and defines how particles drift in outer space. V means the movement on the coordinates (+1, 0), and H means the movement of (0, +1). For example, a particle given wave energy called VHHV drifts in the universe on the trajectories (2, 1), (2, 2), (2, 3) and then reaches the coordinates (3, 3).

In addition, there are multiple warp holes in outer space, which affect the trajectory of particles. The warp hole has an entrance and an exit, and when a particle moves to the entrance of the warp hole, it always warps to the coordinates of the exit. If the coordinates of the entrance and exit of the i-th warp hole are (ai, bi), (ci, di), the condition ai ≤ ci, bi ≤ di, (ai, bi) ≠ (ci, di) is satisfied. It is guaranteed that the entrance to the warp hole does not exist at the same coordinates as the entrance to other warp holes or at (1, 1). However, there may be multiple exits in the same location, or one warp hole exit may have another warp hole entrance (in this case, warp consecutively).

For example, if there is a warp hole with (1, 2) as the inlet and (3, 2) as the exit, the particles given HH and wave energy move to (1, 2) and then (3, 2). Warp to 2) and reach (3, 3).

When particles are given wave energy, they move according to it in an instant. When all the particles reach the destination at the same time, they are automatically reconstructed into the original substance.

You are a programmer of Japan Aerospace Exploration Agency. Since the target coordinates (N, M) of the transfer and the coordinate pairs of K warp holes are given, please write a program to find the maximum mass of the substance that can be transferred at one time. The answer can be very large, so print the remainder divided by 1,000,000,007.

Notes on Test Cases

Multiple datasets are given in the above input format. Create a program that outputs each data set in the above output format.

When N, M, K are all 0, it indicates the end of input.

<!-



Input


NMK
a1 b1 c1 d1
...
aK bK cK dK

Satisfy 1 ≤ N, M ≤ 105, 0 ≤ K ≤ 103. Also, for any 1 ≤ i ≤ K, ai ≤ ci, bi ≤ di, (ai, bi) ≠ (ci, di) is satisfied.

Output

Divide the maximum mass by 1,000,000,007 and output the remainder in one line.

Examples

Input

4 4 1
2 2 3 3
1 4 1
1 2 1 3
5 5 2
2 2 3 4
3 3 5 3
5 5 3
4 4 5 5
2 2 3 3
3 3 4 4
100000 100000 1
2 2 99999 99999
1 1 0
0 0 0


Output

12
1
26
18
615667476
1


Input

4 4 1
2 2 3 3


Output

12


Input

1 4 1
1 2 1 3


Output

1


Input

5 5 2
2 2 3 4
3 3 5 3


Output

26


Input

5 5 3
4 4 5 5
2 2 3 3
3 3 4 4


Output

18


Input

100000 100000 1
2 2 99999 99999


Output

615667476


Input

1 1 0


Output

1

### Response

```cpp
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



#define SIZE 200005

struct Info{
	Info(ll arg_row1,ll arg_col1,ll arg_row2,ll arg_col2){
		row1 = arg_row1;
		col1 = arg_col1;
		row2 = arg_row2;
		col2 = arg_col2;
	}
	bool operator<(const struct Info &arg) const{

		if(row1 != arg.row1){

			return row1 < arg.row1;
		}else{

			return col1 < arg.col1;
		}
	}

	ll row1,col1,row2,col2;
};

ll H,W,K;
ll dp[1005];
ll fact[SIZE];


ll extgcd(ll a,ll b,ll &x,ll &y){
	ll d = a;
	if(b != 0){
		d = extgcd(b,a%b,y,x);
		y -= (a/b)*x;
	}else{
		x = 1;
		y = 0;
	}
	return d;
}

ll mod_pow(ll x,ll count, ll mod){

	if(count == 0)return 1;
	ll ret = mod_pow((x*x)%mod,count/2,mod);
	if(count%2 == 1){

		ret = (ret*x)%mod;
	}
	return ret;
}


ll mod_inverse(ll a,ll m){
    ll x,y;
    extgcd(a,m,x,y);
    return (m+x%m)%m;
}

ll mod_fact(ll n,ll p,ll &e){
	e = 0;
	if(n == 0)return 1;

	int res = mod_fact(n/p,p,e);
	e += n/p;

	if(n/p%2 != 0)return res*(p-fact[n%p])%p;
	return res*fact[n%p]%p;
}


ll nCm(ll n,ll m,ll p){
   if(n < m) return 0;
   ll e1,e2,e3;
   ll a1 = mod_fact(n,p,e1),a2 = mod_fact(m,p,e2),a3 = mod_fact(n-m,p,e3);
   if(e1 > e2+e3)return 0;
   return a1 * mod_inverse(a2*a3%p,p)%p;
}

void func(){

	vector<Info> V;

	ll col1,row1,col2,row2;

	for(int loop = 0; loop < K; loop++){

		scanf("%lld %lld %lld %lld",&col1,&row1,&col2,&row2);

		V.push_back(Info(row1,col1,row2,col2));
	}

	sort(V.begin(),V.end());

	ll minus,A,B;

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

		dp[i] = nCm(V[i].row1+V[i].col1-2,V[i].row1-1,MOD);

		for(int k = 0; k <= i-1; k++){
			if(V[k].col1 > V[i].col1)continue;

			A = nCm((V[i].row1-V[k].row1+V[i].col1-V[k].col1),V[i].row1-V[k].row1,MOD);
			if(V[k].col2 > V[i].col1 || V[k].row2 > V[i].row1){

				B = 0;

			}else{

				B = nCm((V[i].row1-V[k].row2+V[i].col1-V[k].col2),V[i].row1-V[k].row2,MOD);
			}

			minus = (A-B+MOD)%MOD;
			minus *= dp[k];
			minus %= MOD;

			dp[i] = (dp[i]-minus+MOD)%MOD;
		}
	}

	ll ans = nCm(H+W-2,H-1,MOD);

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

		A = nCm(H-V[i].row1+W-V[i].col1,H-V[i].row1,MOD);
		B = nCm(H-V[i].row2+W-V[i].col2,H-V[i].row2,MOD);

		minus = (A-B+MOD)%MOD;
		minus *= dp[i];
		minus %= MOD;

		ans = (ans-minus+MOD)%MOD;
	}

	printf("%lld\n",ans);
}


int main(){

	fact[0] = 1;
	for(ll i = 1; i < SIZE; i++){
		fact[i] = i*fact[i-1];
		fact[i] %= MOD;
	}

	while(true){

		scanf("%lld %lld %lld",&W,&H,&K);
		if(H == 0 && W == 0 && K == 0)break;

		func();
	}

	return 0;
}


```