The life of a student is very diverse. Every day, a student can be in 4 states: at home, on the way from home to university, at the university, and on the way back home. To make life more interesting, the student decided to take a new route every day, without visiting the same place twice in one day.

Our student lives in a city with streets that run strictly from west to east or from north to south. There are a total of N streets running from north to south and M streets running from west to east. The distances between two neighboring parallel streets are equal, and at the intersections of the streets, there are junctions where the student can turn in any direction if there is a road. Thus, we can say that the student lives on a square grid of size N × M, with intersections located at coordinates (i, j). There may be no road between some neighboring intersections. For example, if there is no road between intersections (i, j) and (i, j+1), then the student cannot go directly from (i, j) to (i, j+1). Similarly, if there is no road between (i, j) and (i+1, j).

The student’s home is located at the coordinates (1, 1), and the university is at the coordinates (N, M). The student plans to walk from home to the university and then back, sometimes turning at intersections. During this process, the student does not want to walk in the direction opposite to their goal. Thus, if the student, while walking from home to the university, finds themselves at the coordinates (i, j), they will never go towards (i−1, j) or (i, j−1). Similarly, if the student is walking from the university home, they will not go from (i, j) to (i+1, j) or (i, j+1). The student is also not interested in passing through the same intersection twice in one day. This means that if the student has visited a certain intersection (i, j) while going to the university, they will not return to intersection (i, j) on the way back.

Help the student calculate the maximum number of days after which they will have to walk the same route they took on one of the previous days.

The first line contains N and M — the number of streets running from west to east and the number of streets running from north to south (1 ≤ N, M ≤ 300).

The second line contains K — the number of missing roads in the city (0 ≤ K ≤ 10⁵).

The next K lines contain numbers a_i, b_i, c_i, d_i — which means that there is no road between intersections (a_i, b_i) and (c_i, d_i) (1 ≤ a_i, c_i ≤ N, 1 ≤ b_i, d_i ≤ M). It is guaranteed that |a_i−c_i|+|b_i−d_i|=1 and no missing road is entered twice. Roads exist between all other neighboring intersections.

In one line, output the maximum number of days after which the student will walk the same route twice. Since the number can be very large, output the answer modulo 10⁹ + 7. If there is no route that satisfies all conditions, output 0.