Розрізанння прямокутника
На координатній площині задано прямокутник, висота якого h, а ширина w. Всередині прямокутника задано відрізки, паралельні осям координат і з кінцями, які мають цілочисельні координати.
Прямокутник планується розрізати на декілька частин горизонтальними або вертикальними розрізами. За один крок дозволяється розрізати на дві не порожні прямокутні частини лише один з наявних на цьому кроці прямокутників. При цьому забороняється при розрізі перетинати довільний з заданих відрізків.
Потрібно написати програму, яка дозволить знайти кількість способів розрізання заданого прямокутника на k частин вертикальними і горизонтальними розрізами. Способи, які відрізняються порядком проведення розрізів, вважаються різними.
Вхідні дані
Перший рядок містить розміри прямокутника - цілі числа h та w (1 ≤ h, w ≤ 8). Другий рядок містить кількість частин k, на які потрібно розрізати прямокутник (1 ≤ k ≤ hw). Третій рядок містить кількість cnt (0 ≤ cnt ≤ 10) заданих всередині прямокутника відрізків. Наступні cnt рядків містять опис цих відрізків, тобто, кажен рядок містить чотири цілих числа x_1, y_1, x_2, y_2 (0 ≤ x_1 ≤ x_2 ≤ w, 0 ≤ y_1 ≤ y_2 ≤ h) - координати кінців відрізка.
Вихідні дані
Вивести шукану кількість способів розрізання заданого прямокутника. Відповідь вивести за модулем 2^30.