Problem description

Małgosia jest fanką sportów zimowych. Dzisiaj bierze udział w slalomie. Trasa slalomu jest przedstawiona jako prostokąt złożony z N × M pól. Małgosia startuje w polu o współrzędnych (1,1), a jej celem jest dotarcie do mety, znajdującej się w polu (N,M). Z pola (x,y) można zjechać na pole (x+1,y) oraz (x,y+1).

Na trasie rozłożone są przeszkody – prostokątne obszary, na które nie można wjechać. Małgosia może ominąć każdą przeszkodę na dwa sposoby – przeszkoda może znajdować się po lewej lub prawej stronie ścieżki wyznaczonej przez jej zjazd. Dziewczyna zastanawia się, na ile sposobów może przejechać trasę. Dwa sposoby uznajemy za różne, kiedy jakaś przeszkoda jest ominięta w inny sposób.

Poniższe rysunki przedstawiają sposoby przejechania tras z testów przykładowych.

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby N, M, K, oznaczające wymiary trasy oraz ilość przeszkód. W każdym z kolejnych K wierszy znajdują się cztery liczby naturalne x₁, y₁, x₂, y₂ (1 ≤ x₁ ≤ x₂ ≤ N, 1 ≤ y₁ ≤ y₂ ≤ M), oznaczające współrzędne lewego-dolnego oraz prawego-górnego pola należącego do przeszkody. Przeszkody nie nachodzą na siebie, ale pola różnych przeszkód mogą ze sobą sąsiadować.

Wyjście

W pierwszym wierszu wyjścia wypisz jedną liczbę, oznaczającą ilość różnych sposobów na przejechanie trasy modulo 10⁹ + 7.

Ograniczenia

3 ≤ N, M ≤ 100 000, 0 ≤ K ≤ 100 000

Podzadania

Przykład

3 3 0

1

4 5 1
2 2 3 4

2

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

3