Розрізання прямокутника#557

Розрізання прямокутника

1 секунда

64 мегабайти

Дуже легка

На координатній площині задано прямокутник з висотою $h$ та шириною $w$ . Усередині цього прямокутника розміщено відрізки, паралельні до координатних осей, з цілими координатами кінців.

Планується розрізати прямокутник на кілька частин горизонтальними та вертикальними розрізами. На кожному кроці ви можете розділити будь-який існуючий прямокутник на дві непорожні прямокутні частини горизонтальним або вертикальним розрізом. Заборонено робити розріз, який перетинає будь-який з даних відрізків усередині прямокутника.

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

Вхідні дані

У першому рядку задано два цілих числа $h$ і $w$ ( $1 \leq h, w \leq 8$ 1 \le h, w \le 8) — висота і ширина прямокутника.

У другому рядку задано одне ціле число $k$ ( $1 \leq k \leq h w$ 1 \le k \le hw) — кількість частин, на які треба розділити прямокутник.

У третьому рядку задано одне ціле число $cnt$ ( $0 \leq cnt \leq 10$ 0 \le \text{cnt} \le 10) — кількість відрізків усередині прямокутника.

Кожен з наступних $cnt$ рядків містить по чотири цілих числа $x_{1}$ x_1, $y_{1}$ y_1, $x_{2}$ x_2, $y_{2}$ y_2 ( $0 \leq x_{1} \leq x_{2} \leq w$ 0 \le x_1 \le x_2 \le w, $0 \leq y_{1} \leq y_{2} \leq h$ 0 \le y_1 \le y_2 \le h) — координати кінців відрізка.

Вихідні дані

Виведіть кількість способів розділити даний прямокутник. Відповідь виведіть за модулем $2^{30}$ 2^{30}.

Приклади

Приклад 1