Cutting rectangle#557
A rectangle with height and width is given on the coordinate plane. Inside this rectangle, there are segments parallel to the coordinate axes, with integer coordinates at their endpoints.
It is planned to cut the rectangle into several parts with horizontal and vertical cuts. At each step, you may split any existing rectangle into two non-empty rectangular parts with a horizontal or vertical cut. You are not allowed to make a cut that crosses any of the given segments inside the rectangle.
Write a program to determine the number of ways to cut the given rectangle into parts using horizontal and vertical cuts. Ways that differ in the order of the cuts are considered different.
The first line contains two integers and (1 \le h, w \le 8) — the height and width of the rectangle.
The second line contains one integer (1 \le k \le hw) — the number of parts into which the rectangle must be divided.
The third line contains one integer (0 \le \text{cnt} \le 10) — the number of segments inside the rectangle.
Each of the next lines contains four integers x_1, y_1, x_2, y_2 (0 \le x_1 \le x_2 \le w, 0 \le y_1 \le y_2 \le h) — the endpoints' coordinates of a segment.
Print the number of ways to divide the given rectangle. Output the answer modulo 2^{30}.
Example 1