Düzbucaqlının kəsilməsi#557
Na koordinat müstəvisində hündürlüyü , eni 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. Hər addımda istənilən mövcud düzbucaqlını üfüqi və ya şaquli bir kəsiklə iki boş olmayan düzbucaqlı hissəyə bölmək olar. Bu zaman düzbucaqlının daxilində verilmiş istənilən parçanı kəsmək olmaz.
Verilmiş düzbucaqlını hissəyə üfüqi və şaquli kəsiklərlə bölmək üsullarının sayını tapmaq üçün bir proqram yazın. Kəsiklərin müxtəlif ardıcıllığı fərqli üsul hesab olunur.
Birinci sətir iki tam ədəd və (1 \le h, w \le 8) — düzbucaqlının hündürlüyü və eni.
İkinci sətir bir tam ədəd (1 \le k \le hw) — düzbucaqlını neçə hissəyə bölmək lazım olduğunu göstərir.
Üçüncü sətir bir tam ədəd (0 \le \text{cnt} \le 10) — düzbucaqlı daxilində verilmiş parçaların sayıdır.
Növbəti sətrin hər birində dörd tam ədəd x_1, y_1, x_2, y_2 (0 \le x_1 \le x_2 \le w, 0 \le y_1 \le y_2 \le h) — parçalardan birinin uclarının koordinatları verilir.
Verilmiş düzbucaqlını bölmək üsullarının sayını tapıb çap edin. Cavabı 2^{30} modulu ilə çıxarın.
Nümunə 1