7950번 - Szaszłyki 다국어

Witek przygotowuje szaszłyki na grilla. Ustalił listę możliwych składników, które będzie nadziewał na patyczki i teraz zastanawia się w jaki sposób to zrobić. Zauważył bowiem, że pewne produkty nie mogą być nadziewane obok siebie, gdyż psuje to smak potrawy. Także pewne kombinacje trzech kolejnych składników smakują nieciekawie. Przykładowo oznaczmy poprzez a kawałek ananasa natomiast przez b kawałek baraniny. Okazuje się, że dwa kawałki ananasa obok siebie nie tyle źle smakują, ale są w złym guście. Niedobrze jest również jeśli trzy kolejne składniki okazują się być baraniną. Notujemy powyższe uwagi poprzez zabronione kombinacje aa oraz bbb. Warto zauważyć, że szaszłyk nie ulega odwracaniu – jest zawsze spożywany począwszy od lewego końca i stąd także w kombinacjach zabronionych istotna jest kolejność liter. Gdy teraz przyjmiemy, że przygotowujemy szaszłyki nadziewając dokładnie 3 składniki na patyczek, to występują 4 możliwości przygotowania szaszłyka: −aba−, −abb−, −bab−, −bba−. Ponieważ Witek podchodzi do wszystkich spraw bardzo poważnie postanowił napisać program, który policzy ile różnych szaszłyków może uzyskać z produktów, które przygotował. Pomóż mu sprawdzić poprawność programu! Wystarczy gdy obliczysz liczbę możliwych szaszłyków modulo zadana liczba.

Pierwsza linia wejścia zawiera małą liczbę całkowitą z – liczbę zestawów danych występujących kolejno po sobie. Opis jednego zestawu jest następujący:

W pierwszej linii znajdują się liczby całkowite m, n, p, k oddzielone spacjami oznaczające odpowiednio podstawę modulo, długość szaszłyka, liczbę różnych produktów oraz liczbę kombinacji zabronionych (1 ≤ m, n ≤ 1000, 1 ≤ p ≤ 26, 0 ≤ k ≤ p² + p³). W k następnych liniach znajdują się opisy kombinacji zabronionych. Para zabroniona opisana jest przez dwie występujące po sobie małe litery alfabetu angielskiego. Jeśli przez ℓ_j oznaczymy j-tą literę alfabetu angielskiego, to jedyny dopuszczalny opis jest postaci ℓ_j1 ℓ_j2, gdzie 1 ≤ j₁, j₂ ≤ p. Analogicznie, trójka zabroniona opisana jest przez ciąg ℓ_j1 ℓ_j2 ℓ_j3, gdzie 1 ≤ j₁, j₂, j₃ ≤ p.

Dla każdego zestawu danych wypisz liczbę różnych szaszłyków spełniających zadane warunki modulo m.