1000 - 寄り道

問題

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個のショップの座標x_i,y_iが与えられるので、YTAくんの家からYDKくんの家までの最短経路のうちすべての店を通ることができる経路が何通りあるのか求めてください。
ただし、答えは非常に大きくなることがあるため10⁹+7で割った余りを出力してください。

入力

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

出力

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

入出力例

入力例

5 5 2
1 2
3 3

出力例

18