Robotların yarışı#8714
Bu gün Berlandiyada illik robot yarışı keçirilir. İvan da iştirakçılardan biridir. Yarış başlamadan əvvəl, o, robotların yarışacağı sahənin necə olduğunu öyrənmək istəyir. Yarış sahəsi n * m ölçülü düzbucaqlıdır və nm ədəd vahid hüceyrəyə bölünmüşdür. Düzbucaqlının sətirləri 1-dən n-ə, sütunları isə 1-dən m-ə qədər nömrələnmişdir. i-ci sətir və j-ci sütunun kəsişməsində yerləşən hüceyrəni (i, j) kimi qeyd edəcəyik. Sahədəki hər bir cüt qonşu hüceyrə arasında maneə ola bilər.
Yarışda n robot iştirak edir. Əvvəlcə onlar birinci sütunun hüceyrələrində yerləşirlər: (1, 1), (2, 1), ..., (n, 1). Finiş isə (n, m) hüceyrəsidir. Yarış başladıqda, hər bir robot finiş istiqamətində hərəkət etməyə başlayır. (i, j) hüceyrəsindən robot ya (i + 1, j) hüceyrəsinə, ya da (i, j + 1) hüceyrəsinə keçə bilər. Əgər robotun olduğu hüceyrə ilə keçəcəyi hüceyrə arasında maneə yoxdursa, robot dərhal qonşu hüceyrəyə keçir. Əgər hüceyrələr arasında maneə varsa, robot bu keçid üçün bir saniyə sərf edir.
Hər bir robot əvvəlcədən sahədəki maneələrin harada yerləşdiyini bilir və finiş hüceyrəsinə minimal vaxtla keçən yolla hərəkət edir. Robotlar çox kiçikdir, buna görə bir neçə robot eyni anda bir hüceyrədə ola bilər və bir-birinə mane olmur. Yarış sahəsini ədalətli adlandıracağıq, əgər start mövqeyindən finişə çatmaq üçün lazım olan minimal vaxt bütün robotlar üçün eynidirsə.
İvan yarış sahəsinə nəzər salmağa vaxt tapdı və onun haqqında bəzi məlumatları yadda saxladı. Yəni, bəzi qonşu hüceyrə cütləri arasında maneə olub-olmadığını dəqiq bilir. O, həmçinin əmindir ki, yarış sahəsi ədalətlidir. İvana maraqlı gəldi ki, bu şərtlərə cavab verən neçə sahə mövcuddur. Cavab çox böyük ola biləcəyi üçün İvanı yalnız 998244353-ə bölünmədən qalan qalıq maraqlandırır.
Birinci sətir yarış sahəsinin ölçüləri olan iki tam ədəd n və m-i ehtiva edir (1 ≤ n ≤ 5, 1 ≤ m ≤ 15). İkinci sətir İvanın hüceyrələr arasında maneə olub-olmadığını bildiyi cütlərin sayı olan tək bir ədəd k-ni ehtiva edir (0 ≤ k ≤ 2nm - n - m).
Növbəti k sətirin hər biri beş tam ədəd r[1], c[1], r[2], c[2] və w-ni ehtiva edir (1 ≤ r[1] ≤ r[2] ≤ n, 1 ≤ c[1] ≤ c[2] ≤ m, 0 ≤ w ≤ 1). Əgər w = 0-dırsa, (r[1], c[1]) və (r[2], c[2]) hüceyrələri arasında maneə yoxdur. Əgər w = 1-dirsə, hüceyrələr arasında maneə var. Zəmanət verilir ki, (r[1], c[1]) və (r[2], c[2]) hüceyrələri qonşudur. Zəmanət verilir ki, heç bir qonşu hüceyrə cütü girişdə iki dəfə qeyd olunmayacaq.
Yeganə ədəd çıxarın - İvanın bütün şərtlərinə cavab verən ədalətli sahələrin sayının 998244353-ə bölünməsindən qalan qalıq.
Nümunədəki test, bərk xətlər maneəni, nöqtəli xətlər isə maneənin olmadığını göstərir.
Nümunə 1