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.