Задача C. Разрезание прямоугольника

Автор:Методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

На координатной плоскости задан прямоугольник, высота которого h, а ширина — w. Внутри прямоугольника задано n отрезков, параллельных осям координат.

Прямоугольник планируется разрезать на несколько частей горизонтальными или вертикальными разрезами. За один шаг разрешается разрезать на две непустые прямоугольные части только один из имеющихся на этом шаге прямоугольников. Размеры получившихся частей должны быть целочисленными. Линия разреза не должна пересекать ни один из заданных отрезков.

Требуется написать программу, позволяющую найти количество способов разрезания исходного прямоугольника на k частей. Способы, отличающиеся порядком проведения разрезов, считаются различными.

Формат входного файла

Входной файл содержит целые числа h w k n. Далее следует n четвёрок целых чисел X1 Y1 X2 Y2 — координаты концов отрезков.

Формат выходного файла

Выходной файл должен содержать целое число — искомое количество способов разрезания исходного прямоугольника. Ответ должен быть представлен по модулю 230.

Ограничения

1 ≤ h, w ≤ 8

1 ≤ k ≤ h × w

0 ≤ n ≤ 10

0 ≤ X1 ≤ X2 ≤ w, 0 ≤ Y1 ≤ Y2 ≤ h

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2 2
4
0
4
2
8 8
20
0
767625216
3
4 4
2
2
2 0 2 3
2 3 4 3
3

0.102s 0.019s 15