Miruna are un seif care este împărţit în mai multe compartimente, dispuse sub forma unei matrice cu N linii şi M coloane. Astfel, fiecărui compartiment îi pot fi asociate două coordonate x şi y reprezentand linia, respectiv coloana din care face parte.
Pentru a deschide un compartiment, este nevoie de o anumită cheie unică asociată. O echipă de hoţi a reuşit să facă rost de o parte dintre cele N*M chei, însă nu de toate. Se ştie faptul că hoţilor le lipsesc exact K chei.
Un compartiment de coordonate (x, y) este considerat a fi în siguranţă dacă sunt îndeplinite următoarele condiţii:
1. Hoţii nu au cheia asociată compartimentului.
2. Hoţii nu au cheia unui alt compartiment de coordonate (z, y), unde z<x şi diferenţa x-z ≤ L (unde L este indicele de siguranţă al seifului).
Cerinţă
Miruna nu ştie care sunt cheile care le lipsesc hoţilor. Fiecare set posibil de câte K chei determină o mulţime de compartimente care sunt în siguranţă. Ea ar dori să ştie câte seturi de K chei determină exact S compartimente care sunt în siguranţă.
Date de intrare
Fişierul de intrare seif.in conţine pe prima linie sunt scrise 5 numere întregi N M K L S, separate prin câte un singur spaţiu, având semnificaţia din enunţ.
Date de ieşire
Fişierul de ieşire seif.out va conţine o singură linie pe care va fi scris numărul de seturi de K chei lipsă pentru care exact S compartimente sunt în siguranţă, modulo 30011.