On the coordinate plane given rectangle, whose height \textbf{h}, and the width - \textbf{w}. Inside the rectangle are given segments, parallel to the axes and the ends that have integer coordinates. The rectangle will be cut into several horizontal or vertical slits. For one step is allowed to cut into two nonempty rectangular parts only one available at this step rectangles. It is prohibited in any cross section of the specified segments. Need to write a program that allows to find ways of cutting the number of source rectangle into \textbf{k} parts of the vertical and horizontal cuts. Methods other than the order of the cuts are different. \InputFile The first line contains the dimensions of the rectangle - the integers \textbf{h} and \textbf{w}\textit{ }(\textbf{1} ≤ \textbf{h}, \textbf{w }≤ \textbf{8}). The second line contains the number \textbf{k }(\textbf{1 }≤ \textbf{k }≤ \textbf{hw}) of parts, which require cutting a rectangle. The third line contains an integer \textbf{cnt }(\textbf{0} ≤ \textbf{cnt }≤ \textbf{10}) - the number given within a rectangle of the segments. Follow \textbf{cnt}\textit{ }lines contain a description of these segments, that is, each line contains four integers \textbf{x_1}, \textbf{y_1}, \textbf{x_2}, \textbf{y_2} (\textbf{0 }≤ \textbf{x_1}\textit{ ≤ }\textbf{x_2} ≤ \textbf{w}, \textbf{0 }≤ \textbf{y_1} ≤ \textbf{y_2} ≤ \textbf{h}) - coordinates all segment. \OutputFile Print the required number of ways of cutting the source rectangle. The answer must be submitted to the modulo \textbf{2^30}.