На координатной плоскости задан прямоугольник, высота которого \textbf{h}, а ширина \textbf{w}. Внутри прямоугольника заданы отрезки, параллельные осям координат и с концами, имеющими целочисленные координаты. Прямоугольник планируется разрезать на несколько частей горизонтальными или вертикальными разрезами. За один шаг разрешается разрезать на две непустые прямоугольные части только один из имеющихся на этом шаге прямоугольников. При этом запрещается при разрезе пересекать любой из заданных отрезков. Требуется написать программу, позволяющую найти количество способов разрезания исходного прямоугольника на \textbf{k} частей вертикальными и горизонтальными разрезами. Способы, отличающиеся порядком проведения разрезов, считаются различными. \InputFile Первая строка содержит размеры прямоугольника - целые числа \textbf{h }и \textbf{w }(\textbf{1 }≤ \textbf{h}, \textbf{w }≤ \textbf{8}). Вторая строка содержит количество частей \textbf{k}, на которые требуется разрезать прямоугольник (\textbf{1 }≤ \textbf{k }≤ \textbf{hw}). Третья строка содержит количество \textbf{cnt} (\textbf{0 }≤ \textbf{cnt }≤ \textbf{10}) заданных внутри прямоугольника отрезков. Последующие \textbf{cnt }строк содержат описания этих отрезков, то есть, каждая строка содержит четыре целых числа \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}) - координаты концов отрезка. \OutputFile Вывести искомое количество способов разрезания исходного прямоугольника. Ответ должен быть представлен по модулю \textbf{2^30}.