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
Dla danych wejściowych:
6 1234 3 2
poprawną odpowiedzią jest:
9
Szukanymi podzbiorami są:
,
,
,
,
,
,
,
oraz
.
Autor zadania: Jakub Radoszewski.