Ogromna wieża
Limit pamięci: 256 MB
Starożytni Babilończycy postanowili zbudować ogromną wieżę.
Wieża będzie składać się z sześciennych bloków
położonych jeden na drugim.
Babilończycy zebrali z całego państwa wiele bloków różnych rozmiarów.
Z ostatniej, nieudanej próby budowy dowiedzieli się, że jeśli ustawią większy blok bezpośrednio na dużo mniejszym, wieża przewróci się.
Zadanie
Zakładamy, że każde dwa bloki są różne, nawet jeśli są jednakowej wielkości.
Dla każdego bloku znasz długość jego boku.
Masz również daną liczbę całkowitą , oznaczającą, że nie wolno położyć bloku bezpośrednio na bloku
dokładnie wtedy, gdy długość boku bloku jest ściśle większa niż plus długość boku bloku .
Oblicz liczbę różnych sposobów zbudowania wieży ze wszystkich bloków.
Ponieważ wynik może być bardzo duży, wypisz resztę z dzielenia go przez .
Specyfikacja wejścia
Pierwszy wiersz wejścia składa się z dwóch liczb całkowitych dodatnich oraz :
liczby bloków oraz tolerancji określonej jak wyżej.
Drugi wiersz zawiera pooddzielanych pojedynczymi odstępami liczb całkowitych; każda z nich jest
długością boku jednego z bloków.
Ograniczenia
Wszystkie liczby na wejściu są całkowite, dodatnie i nie przekraczają .
jest zawsze równe co najmniej 2.
W testach wartych 70 punktów nie przekroczy 70.
Wśród nich są testy warte 45 punktów, w których będzie równe co najwyżej 20.
Wśród tych z kolei są testy warte 10 punktów, w których będzie równe co najwyżej 10.
W części testów całkowita liczba poprawnych wież będzie nie większa niż . Te testy są warte łącznie 30 punktów.
W ostatnich sześciu testach (wartych 30 punktów) będzie większe niż 70. Górne ograniczenie na w tych testach nie jest podane.
Specyfikacja wyjścia
Wypisz jeden wiersz zawierający jedną liczbę całkowitą: liczbę wież, które można zbudować, modulo .
Przykłady
Dla danych wejściowych:
4 1
1 2 3 100
poprawną odpowiedzią jest:
4
Pierwsze trzy bloki można uporządkować w dowolnej kolejności poza oraz . Ostatni blok musi leżeć na spodzie.
Dla danych wejściowych:
6 9
10 20 20 10 10 20
poprawną odpowiedzią jest:
36
Nie można położyć bloku o boku 20 na bloku o boku 10.
Istnieje sześć sposobów uporządkowania bloków o boku 10 i sześć sposobów uporządkowania bloków o boku 20.
Autor zadania: Michal Forisek.