Marsian boşqabları#4955
Mars restoranında fərqli yemək var. Bayram şam yeməyi ardıcıllıqla verilən yeməkdən ibarətdir (burada l = t/2). Bəzi yeməklər bu şam yeməyində bir neçə dəfə təqdim oluna bilər, bəziləri isə heç cür təqdim olunmaya bilər. Şam yeməyi zamanı gətirilən yeməklərin boşqabları bir-birinin üzərinə yığılır. Ofisiant ya yeni yemək gətirir (onun boşqabını yuxarıya əlavə edir), ya da üstdəki boşqab bitdikdə onu götürür. Lakin, hər hansı bir boşqab yalnız ondan sonra qoyulan bütün boşqablar götürüldükdən sonra masadan götürülə bilər (yəni, boşqablar əlavə olunduqları qaydanın əksinə, ardıcıl çıxarılmalıdır).
Bundan əlavə, bəzi yeməklərin müəyyən ardıcıl cütləri üçün xüsusi adət var: bəzi cütləri üçün, yeməyinin boşqabı hələ masada olduqda, yeməyi masaya gətirilə bilməz. Belə cütlərə "qeyri-adi cütlər" deyilir.
Ofisiantın cədvəli, yeməklərin gətirilmə və boşqabların yığılması ardıcıllığıdır. Beləliklə, cədvəl t = 2l əməliyyatdan ibarətdir. Sizin vəzifəniz — yeməkdən ibarət bayram şam yeməyinin neçə fərqli düzgün cədvəlinin mümkün olduğunu, modulu üzrə tapmaqdır.
Girişin birinci sətrində dörd tam ədəd var: (2 \leq p \leq 10^4), (1 \leq t \leq 200, cütdür), (1 \leq n \leq 10) və (1 \leq m \leq 100) — modul qiyməti, cədvəldəki ümumi əməliyyat sayı (t = 2l), restorandakı yeməklərin sayı və qeyri-adi cütlərin sayı.
Növbəti sətrin hər birində iki tam ədəd — və (1 \leq i, j \leq n) verilir, bu o deməkdir ki, yeməyinin boşqabı hələ masada olduqda yeməyi gətirilə bilməz.
Mümkün düzgün cədvəllərin sayını modulu üzrə çıxışa yazın.
Nümunə 1