카드

앨리스와 밥이 다락방에서 카드 여러 벌을 발견했습니다. 어떤 카드는 먼지가 잔뜩 쌓여 있었고, 어떤 벌은 낱장이 빠져 있었으며, 일반적인 카드에는 없는 이상한 그림 카드도 섞여 있었습니다. 그래도 모든 카드에는 한 가지 공통점이 있었는데, 바로 검은색 아니면 빨간색이라는 점입니다.

창의력이 넘치는 두 아이는 발견한 카드를 모두 사용해 다음과 같은 게임을 하기로 했습니다.

먼저 모든 카드를 한데 섞습니다. 그런 다음 덱의 맨 위에서부터 카드를 한 장씩 뒤집어 탁자에 내려놓습니다. 맨 처음 내려놓은 카드가 검은색이거나, 연속으로 나온 검은색 카드의 어떤 극대 구간이 그 길이의 $k$배 이상인 연속된 빨간색 카드 구간 바로 뒤에 놓이지 않는다면 앨리스가 이깁니다. 그렇지 않은 채로 모든 카드를 다 내려놓았다면 밥이 이깁니다.

앨리스는 자신이 이길 가능성이 궁금합니다. 덱을 섞어서 나올 수 있는 모든 배열 가운데 자신이 이기는 배열이 몇 가지인지 알고 싶어 합니다. 같은 색 카드끼리는 서로 구별하지 않습니다. 앨리스는 최근 중국인의 나머지 정리를 배웠으므로, 답을 주어진 소수 $p$로 나눈 나머지만 구하면 충분합니다.

입력의 유일한 줄에 네 정수 $r$, $b$, $k$, $p$가 공백 하나로 구분되어 주어집니다 ($1 \le r, b \le 100\,000$, $1 \le k \le 10$, $2 \le p \le 1\,000\,000\,000$). $r$은 빨간색 카드의 수, $b$는 검은색 카드의 수이며, $p$는 소수입니다.

빨간색 카드 $r$장과 검은색 카드 $b$장으로 이루어진 배열 중 앨리스가 이기는 배열의 수를 $p$로 나눈 나머지를 한 줄에 출력합니다.

$r = 4$, $b = 2$, $k = 1$인 경우를 생각해 봅시다. 빨간색 카드를 R, 검은색 카드를 B로 나타내면 (가장 왼쪽 글자가 덱의 맨 위 카드), 앨리스가 이기는 배열은 정확히 다음과 같습니다: BBRRRR, BRBRRR, BRRBRR, BRRRBR, BRRRRB, RBBRRR. 각 배열에서는 맨 앞 카드가 검은색이거나, 어떤 검은색 카드 구간 바로 앞의 빨간색 카드 구간이 그 검은색 구간보다 짧습니다.