Cards

Alice and Bob found several decks of cards in the attic. Some were dusty, some were incomplete, and some held unusual honor cards that a regular deck does not contain. Even so, every card shared one trait: it was either black or red.

Being creative children, they decided to use all the cards they had found and play the following game.

First they shuffle every card together. Then they reveal the cards one at a time from the top of the deck onto the table. Alice wins if the very first revealed card is black, or if some maximal run of consecutively revealed black cards is not immediately preceded by a run of consecutive red cards whose length is at least $k$ times the length of that black run. Otherwise, once all cards have been revealed, Bob wins.

Alice wants to know her chances, so she asks: over all arrangements of the deck that a shuffle could produce, in how many of them does she win? Cards of the same color are indistinguishable. Because Alice just learned the Chinese remainder theorem, it is enough to report the answer modulo a given prime number $p$.

The only line of input contains four integers $r$, $b$, $k$, and $p$ ($1 \le r, b \le 100\,000$, $1 \le k \le 10$, $2 \le p \le 1\,000\,000\,000$), separated by single spaces. Here $r$ is the number of red cards, $b$ is the number of black cards, and $p$ is a prime number.

Print a single integer: the number of arrangements of $r$ red cards and $b$ black cards in which Alice wins, taken modulo $p$.

Consider $r = 4$, $b = 2$, $k = 1$. Writing R for a red card and B for a black card (the leftmost letter is the card on top of the deck), Alice wins for exactly these arrangements: BBRRRR, BRBRRR, BRRBRR, BRRRBR, BRRRRB, and RBBRRR. In each of them either the first card is black, or a run of black cards is immediately preceded by a run of red cards shorter than that black run.