007 - 平安京ウォーキング

問題

平安京は、道が格子状になっている町として知られている。

平安京に住んでいるねこのホクサイは、パトロールのために毎日自宅から町はずれの秘密の場所まで行かなければならない。しかし、毎日同じ道を通るのは飽き るし、後を付けられる危険もあるので、ホクサイはできるだけ毎日異なる経路を使いたい。その一方で、ホクサイは面倒臭がりなので、目的地から遠ざかるよう な道は通りたくない。

平安京のあちこちの道にはマタタビが落ちていて、ホクサイはマタタビが落ちている道を通ることができない。そのような道を通るとめろめろになってしまうからである。幸いなことに、交差点にはマタタビは落ちていない。

ホクサイは、自宅から秘密の場所までの可能な経路の数を知りたい。ここで、ホクサイの自宅は (0, 0) にあり、秘密の場所は(g_x, g_y)にある。道は x = i (i は整数), y = j (j は整数) に格子状に敷かれている。

入力

入力の1行目には、秘密の場所の座標 (g_x, g_y) が与えられる。これらはいずれも1以上15以下の整数で、空白1個で区切られて与えられる。 2行目にはマタタビが落ちている区間の数 p (0 ≤ p ≤ 100) が与えられ、続くp行にはマタタビが落ちている区間が1行に1区間ずつ与えられる。 p個の区間は互いに異なる。 1区間は x₁ y₁ x₂ y₂ の形で表され、(x₁, y₁) と (x₂, y₂) を端点とする、x軸またはy軸に平行な長さ1の線分である。 x₁, x₂ は [0, g_x] の範囲にあり、y₁, y₂ は [0, g_y] の範囲にある。

出力

可能な経路の数を出力せよ。可能な経路が1つもない場合は "Miserable Hokusai!" と1行に出力せよ。

入力例

2 2
0

1 1
2
0 0 0 1
0 0 1 0

4 3
4
1 0 0 0
3 3 4 3
4 1 4 0
0 2 0 3

15 15
0

出力例

6

Miserable Hokusai!

5

155117520