006 - 寄り道

時間制限 2 秒 / メモリ制限 128 MB / 得点 400 / x 17 /


TLE
2sec
MLE
128MB
得点
400

問題

YDK国は格子状に道があり、横方向にW本,縦方向にH本存在します。
また、道の交差点上には建物があり、各建物は道を座標軸のように見立てて(x,y)のように表しています。

YTAくんは(0,0)、YDKくんは(W-1,H-1)に住んでおり、YTAくんはYDKくんの家に遊びに行こうと考えています。
YDKくんの家に行く途中にはN個のPCショップがあり、YTAくんはすべての店に寄り道してからYDKくんの家に行きたいと思っています。
ただし、YTAくんはYDKくんの家へ最短経路で行きたいと思っているため、PCショップによる際は最短経路上にある場合しかよりません。

YDK国の道の情報W,H、およびN個のショップの座標xi,yiが与えられるので、YTAくんの家からYDKくんの家までの最短経路のうちすべての店を通ることができる経路が何通りあるのか求めてください。
ただし、答えは非常に大きくなることがあるため109+7で割った余りを出力してください。

入力

入力は1+N行からなる。
1行目にはYDK国の情報がW,H(2≦W,H≦106)及び、PCショップの個数N(1≦N≦100)がW,H,Nの順で与えられる。
続くN行にはそれぞれのPCショップの情報xi,yi(0≦x≦W-1,0≦y≦H-1)が与えられる。
YTA,YDKくんの家及び同じ位置には異なるPCショップは存在せず、i<jならばxi≦xjかつyi≦yjを満たす。
また、条件を満たすような経路は一つ以上必ず存在する。

出力

問題文の条件を満たす経路の個数を109+7で割った余りで出力せよ

入出力例

入力例

5 5 2
1 2
3 3

出力例

18