На
координатной плоскости задан прямоугольник, высота которого h, а ширина
— w. Внутри прямоугольника заданы отрезки, параллельные осям координат и
с концами, имеющими целочисленные координаты.
Прямоугольник планируется разрезать
на несколько частей горизонтальными или вертикальными разрезами. За один шаг
разрешается разрезать на две непустые прямоугольные части только один из
имеющихся на этом шаге прямоугольников. При этом запрещается при разрезе
пересекать любой из заданных отрезков.
Требуется написать программу,
позволяющую найти количество способов разрезания исходного прямоугольника на k
частей вертикальными и горизонтальными разрезами. Способы, отличающиеся
порядком проведения разрезов, считаются различными.
Формат входных данных
Первая строка входного файла содержит
размеры прямоугольника — целые числа h и w (1 £ h, w £ 8). Вторая строка входного
файла содержит целое число k — количество частей, на которые требуется
разрезать прямоугольник (1 £ k £ hw). Третья строка содержит целое число cnt (0 £ cnt £ 10) — количество заданных внутри
прямоугольника отрезков. Последующие cnt строк содержат описания этих
отрезков, то есть, каждая строка содержит четыре целых числа x1,
y1, x2, y2 (0 £ x1 £ x2 £ w, 0 £ y1 £ y2 £ h) — координаты концов
отрезка. Все числа в строках разделены пробелом.
Формат выходных данных
В выходной файл необходимо вывести
одно целое число — искомое количество способов разрезания исходного
прямоугольника. Ответ должен быть представлен по модулю 230.
Пример входного и выходного файлов
|
STDIN
|
STDOUT
|
|
2 2
4
0
|
4
|
|
8 8
20
0
|
767625216
|
|
4 4
2
2
2 0 2 3
2 3 4 3
|
3
|
