Düzbucaqlının kəsilməsi
Koordinat müstəvisində hündürlüyü h, eni isə w olan bir düzbucaqlı verilib. Bu düzbucaqlının daxilində koordinat oxlarına paralel və ucları tam ədədi koordinatlara malik olan parçalar yerləşir.
Düzbucaqlını bir neçə hissəyə üfüqi və ya şaquli kəsiklərlə bölmək planlaşdırılır. Bir addımda yalnız mövcud düzbucaqlılardan birini iki boş olmayan düzbucaqlı hissəyə bölmək mümkündür. Bu zaman verilmiş parçalardan hər hansı birini kəsmək qadağandır.
Verilmiş düzbucaqlını üfüqi və şaquli kəsiklərlə k hissəyə bölmək üsullarının sayını tapmağa imkan verən bir proqram yazmaq lazımdır. Kəsiklərin aparılma ardıcıllığı ilə fərqlənən üsullar müxtəlif hesab olunur.
Giriş verilənləri
Birinci sətir düzbucaqlının ölçülərini - tam ədədlər h və w (1 ≤ h, w ≤ 8) ehtiva edir. İkinci sətir düzbucaqlını bölmək lazım olan hissələrin sayını k (1 ≤ k ≤ hw) ehtiva edir. Üçüncü sətir düzbucaqlının daxilində verilmiş parçaların sayını cnt (0 ≤ cnt ≤ 10) ehtiva edir. Növbəti cnt sətir bu parçaların təsvirini ehtiva edir, yəni, hər sətir dörd tam ədəd x_1, y_1, x_2, y_2 (0 ≤ x_1 ≤ x_2 ≤ w, 0 ≤ y_1 ≤ y_2 ≤ h) - parça uclarının koordinatlarını ehtiva edir.
Çıxış verilənləri
Verilmiş düzbucaqlını bölmək üsullarının sayını tapın. Cavabı 2^30 modulu ilə çıxarın.