Podzbiory [A]

Limit pamięci: 32 MB

Będziemy rozważać podzbiory zbioru , które dla danej liczby całkowitej mają własność, że dla każdej liczby naturalnej co najmniej jedna z liczb: , nie należy do . Zastanawiamy się, ile jest takich podzbiorów, zawierających dokładnie elementów. Niewykluczone, że wynik jest dość spory - dlatego wystarczy nam wiedza o reszcie z dzielenia go przez .

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia cztery liczby całkowite: , , oraz ,
• wyznaczy resztę z dzielenia przez liczby -elementowych podzbiorów zbioru , spełniających wyżej opisaną własność,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym i jedynym wierszu wejścia znajdują się cztery liczby całkowite , , oraz (, , , ), pooddzielane pojedynczymi odstępami.

Wyjście

Pierwszy i jedyny wierszy wyjścia powinien zawierać jedną liczbę całkowitą - resztę z dzielenia przez liczby -elementowych podzbiorów zbioru o rozważanej własności.

Przykład

6 1234 3 2

9

Szukanymi podzbiorami są: , , , , , , , oraz .

Autor zadania: Jakub Radoszewski.