Жизнь студента очень разнообразна. Каждый день студент может побывать в 4 состояниях: дома, на пути из дома в универ, в универе, на пути из универа домой. Чтобы сделать свою жизнь более разнообразной, студент решил путешествовать каждый день новым маршрутом, не посещая одно место дважды в течение одного дня.

Наш студент живет в городе с улицами, которые идут строго с запада на восток или с севера на юг. Всего есть N улиц, которые идут с севера на юг, и M улиц, которые идут с запада на восток. Также в этом городе расстояния между двумя соседними параллельными улицами равны между собой, и на пересечении улиц находятся перекрестки, на которых студент может свернуть в любую сторону, если там есть дорога. То есть можно сказать, что студент живёт на квадратной решётке размера N × M, а в точках с координатами (i, j) находятся перекрестки этого города. Между некоторыми соседними перекрестками может отсутствовать дорога. Так, если между перекрестками (i, j) и (i, j+1) нет дороги, то студент не сможет из (i, j) сразу попасть в (i, j+1). Аналогично, если между (i, j) и (i+1, j) нет дороги.

Дом студента находится в точке с координатами (1, 1), а универ — в точке с координатами (N, M). Студент собирается дойти сначала из дома до универа, а потом обратно, иногда сворачивая на перекрестках. При этом студент не хочет в процессе ходьбы идти в сторону, противоположную от его цели. Так, если студент, пока шёл из дома в универ, оказался в точке с координатами (i, j), то он никогда не пойдет в сторону точки (i−1, j) или (i, j−1). Аналогично, если студент идёт из универа домой, то он не пойдет из (i, j) в (i+1, j) или (i, j+1). Также студенту неинтересно ходить через один перекресток дважды в течение дня. Это значит, что если студент посещал некоторый перекресток (i, j), пока шёл в универ, то на обратном пути он ни за что не окажется в перекрестке (i, j) снова.

Помогите студенту посчитать, через какое максимальное количество дней ему придется пройти тем же маршрутом, которым он ходил ранее в один из дней.

В первой строке даны N и M — число улиц, идущих с запада на восток, и число улиц, идущих с севера на юг (1 ≤ N, M ≤ 300).

Во второй строке дано K — число отсутствующих дорог в городе (0 ≤ K ≤ 10⁵).

В следующих K строках даны числа a_i, b_i, c_i, d_i — означает, что между перекрестками (a_i, b_i) и (c_i, d_i) нет дороги (1 ≤ a_i, c_i ≤ N, 1 ≤ b_i, d_i ≤ M). Гарантируется, что |a_i−c_i|+|b_i−d_i|=1 и ни одну отсутствующую дорогу не ввели дважды. Между остальными соседними перекрестками дороги есть.

В одной строке выведите максимальное число дней, через которое студент пройдет по одному маршруту дважды. Так как число может быть очень большим, выведите ответ по модулю 10⁹ + 7. Если нет ни одного маршрута, выполняющего все условия, выведите 0.