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.