20XX年、遠く離れた場所に対する効率的な物質転送方式が確立され、人類の宇宙への進出はますます加速されることになった。この転送方式は、より遠くに物質を転送しようとすると、原則的により大きな物質の転送が可能になる点で革新的であった。転送方式の詳細を次に記す。
まず転送対象となる物質は、スタート座標(1, 1)にて単位質量毎のパーティクルに分割される。各パーティクルには、各々異なる波動エネルギーが与えられなければならない。波動エネルギーは、VとHからなる任意の長さの文字列で表現され、パーティクルの宇宙空間における漂い方を規定する。Vは座標上(+1, 0)の移動を意味し、Hは(0, +1)の移動を意味する。例えば、VHHVという波動エネルギーが与えられたパーティクルは、(2, 1), (2, 2), (2, 3) という軌跡で宇宙を漂った後、座標(3, 3)に辿り着く。
また、宇宙空間には複数のワープホールが存在し、パーティクルの軌跡に影響を与える。ワープホールには入口と出口があり、パーティクルがワープホールの入口に移動した場合、必ず出口の座標にワープすることになる。i番目のワープホールの入口と出口の座標を(ai, bi), (ci, di)とすると、ai ≤ ci, bi ≤ di, (ai, bi) ≠ (ci, di)の条件が満たされており、ワープホールの入口は、他のワープホールの入口と同じ座標や、(1, 1)には存在しないことが保証されている。ただし、複数の出口が同じ場所にあったり、あるワープホールの出口に別のワープホールの入口がある場合はある(この場合は連続でワープする)。
例えば、(1, 2)を入口とし、(3, 2)を出口とするワープホールが存在した場合、HHと波動エネルギーを与えられたパーティクルは、(1, 2)へ移動後、(3, 2)へワープし、 (3, 3)へと辿り着く。
パーティクルは波動エネルギーを与えられると一瞬でそれに従って移動する。全てのパーティクルが同時に目的地点へ辿り着くと、自動的に元の物質へと再構成される。
あなたは宇宙開発機構のプログラマである。転送の目的座標 (N, M) と K 個のワープホールの座標対が与えられるので、一度に転送可能な物質の最大質量を求めるプログラムを書いてほしい。答えは非常に大きい数になる可能性があるため、1,000,000,007で割った余りを出力せよ。
N M K a1 b1 c1 d1 ... aK bK cK dK
1 ≤ N,M ≤ 105, 0 ≤ K ≤ 103 を満たす。また、 任意の 1 ≤ i ≤ K に対して ai ≤ ci, bi ≤ di, (ai, bi) ≠ (ci, di) を満たす。
最大質量を 1,000,000,007 で割ったあまりを1行で出力せよ。
上記入力形式で複数のデータセットが与えられます。各データセットに対して上記出力形式で出力を行うプログラムを作成して下さい。
N, M, K がすべて 0 のとき入力の終わりを示します。
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
12 1 26 18 615667476 1