Balıqlar
Şahrazadın nağıllarında deyilir ki, səhranın ortasında bir göl var. Əvvəlcə göldə F balıq var idi. Dünyanın ən yaxşı qiymətli daşlarından K müxtəlif növ seçilmişdi və belə oldu ki, hər bir balıq dəqiq bir növ qiymətli daşı uddu. K F-dən az ola bildiyi üçün iki və ya daha çox balıq eyni növ qiymətli daşları uda bilərdi.
Zaman keçdikcə bəzi balıqlar digər balıqları yedi. Bir balıq digər balığı yalnız o halda yeyə bilərdi ki, onun uzunluğu ən azı iki dəfə çox olsun (balıq A balıq B-ni yalnız o halda yeyə bilərdi ki, LA >= 2 * LB). Balığın digər balıqları yemək qərarını necə verdiyinə dair heç bir qayda yoxdur. Balıq müəyyən sayda kiçik balıqları yemək qərarına gələ bilərdi, eyni zamanda bəzi balıqlar digər balıqları yeməmək qərarına gələ bilərdi, baxmayaraq ki, bunu edə bilərdilər. Balıq kiçik balığı yedikdə, onun uzunluğu dəyişmirdi, lakin kiçik balığın mədəsindəki bütün qiymətli daşlar zərər görmədən böyük balığın mədəsinə düşürdü.
Şahrazadın nağıllarında deyilir ki, əgər gölə girsəniz, dəqiq bir balıq tuta və onun mədəsindəki bütün qiymətli daşları götürə bilərsiniz. Siz, əlbəttə, taleyinizi sınamaq istəyirsiniz, lakin səyahətə başlamazdan əvvəl, bir balıq tutaraq əldə edə biləcəyiniz müxtəlif qiymətli daş kombinasiyalarının sayını öyrənməlisiniz.
Hər bir balığın uzunluğuna və hər bir balığın əvvəlcə udduğu qiymətli daşın növünə görə, hər hansı bir balığın mədəsində ola biləcək müxtəlif qiymətli daş kombinasiyalarının sayını, verilmiş tam ədəd M modulunda müəyyən edən bir proqram yazın. Kombinasiya yalnız K növ qiymətli daşların sayına görə müəyyən edilir. Qiymətli daşlar arasında sıra anlayışı yoxdur və eyni növ iki qiymətli daş fərqlənmir.
1 <= F <= 500 000 (F – göldəki balıqların ilkin sayı) 1 <= K <= F (K – müxtəlif qiymətli daş növlərinin sayı) 2 <= M <= 30 000 1 <= LX <= 1 000 000 000 (LX – balıq X-in uzunluğu)
Giriş verilənləri
Proqramınız standart girişdən aşağıdakı məlumatları oxumalıdır:
1-ci sətir göldəki balıqların ilkin sayını göstərən tam ədəd F ehtiva edir.
2-ci sətir müxtəlif qiymətli daş növlərinin sayını göstərən tam ədəd K ehtiva edir. Qiymətli daş növləri 1-dən K-yə qədər olan ədədlərlə təqdim olunur.
3-cü sətir tam ədəd M ehtiva edir.
Növbəti F sətirin hər biri bir balığı təsvir edir, bir boşluqla ayrılmış 2 tam ədəd istifadə edərək: balığın uzunluğu və bu balığın əvvəlcə udduğu qiymətli daşın növü.
Qeyd. Həllin qiymətləndirilməsi üçün istifadə olunan bütün testlərdə K növünün hər birindən ən azı bir qiymətli daşın mövcud olduğu təmin edilir.
Çıxış verilənləri
Proqramınız standart çıxışa 0-dan (M-1)-ə qədər olan bir tam ədəd ehtiva edən bir sətir çıxarmalıdır – qiymətli daşların müxtəlif mümkün kombinasiyalarının sayı, M ədədinin modulunda.
Qeyd etmək lazımdır ki, məsələnin həlli üçün M ədədinin heç bir başqa mənası yoxdur, yalnız hesablamaları asanlaşdırmaq üçün.