Karty [B]
Limit pamięci: 32 MB
Jaś i Staś znaleźli na strychu kilka talii kart.
Niektóre były bardzo zakurzone, inne niekompletne, a jeszcze inne składały się
z dziwnych figur, niespotykanych w zwyczajnych kartach do gry.
Wszystkie karty miały jednak wspólną cechę: były koloru czarnego lub czerwonego.
Jaś i Staś mają głowy zawsze pełne pomysłów.
Postanowili wykorzystać znalezione karty i zagrać w następującą grę.
Na początku rozgrywki tasują wszystkie karty.
Następnie wykładają po kolei karty z wierzchu talii na stół.
Jeśli pierwsza wyłożona karta jest czarna lub pewna seria kolejno wykładanych
czarnych kart nie jest bezpośrednio poprzedzona razy od niej dłuższą serią kart
czerwonych, to grę wygrywa Staś.
W przeciwnym przypadku, po wyłożeniu wszystkich kart na stół gra kończy się zwycięstwem Jasia.
Staś chciałby ocenić, jakie ma szanse na zwycięstwo, dlatego zastanawia się,
dla ilu układów kart powstałych po przetasowaniu wygra on z Jasiem.
Zakładamy, że wszystkie karty danego koloru są od siebie nierozróżnialne.
Staś usłyszał ostatnio o Chińskim Twierdzeniu o Resztach, dlatego wystarczy mu,
gdy pozna wynik modulo pewna liczba pierwsza .
Wejście
W pierwszym i jedynym wierszu standardowego wejścia znajdują się cztery liczby
całkowite , , oraz
(, , ),
pooddzielane pojedynczymi odstępami.
Liczba oznacza liczbę czerwonych kart w talii, zaś - liczbę czarnych kart.
Liczba jest pierwsza.
Wyjście
W pierwszym i jedynym wierszu standardowego wyjścia wypisz resztę z dzielenia
przez liczby układów kart składających się z kart czerwonych i
kart czarnych, dla których rozgrywka zakończy się wygraną Stasia.
Przykład
Dla danych wejściowych:
4 2 1 17
poprawną odpowiedzią jest:
6
Wyjaśnienie do przykładu.
W tym przypadku Staś wygra, jeżeli albo pierwsza karta będzie czarna, albo
jakaś seria kart czarnych poprzedzona jest bezpośrednio krótszą od niej serią kart
czerwonych.
Jeśli kartę czerwoną oznaczymy przez R, a czarną przez B,
to układy, dla których wygrywa Staś, to
(pierwsza litera oznacza kartę z wierzchu talii):
BBRRRR,
BRBRRR,
BRRBRR,
BRRRBR,
BRRRRB oraz
RBBRRR.
Autor zadania: Łukasz Bieniasz-Krzywiec.