Alice nad Bob have found a few decks of cards at the attic. Some of them were very dusty, some incomplete, and some contained strange honor cards that cannot be found among regular playing cards. However, all cards had one characteristic in common: they were either black or red. Alice and Bob are very creative children. They decided to use all the cards they have found and play the following game.

In the beginning of the game children shuffle all the cards. Afterwards, they play the cards one by one from the top of the deck onto the table. If the first played card is black or some sequence of consecutively played black cards is $ not $ immediately preceded by a k times longer sequence of consecutive red cards, then Alice wins the game. In the opposite case, after all cards have been played, Bob wins the game.

Alice would like to find out what is her chance of winning, so she is wondering for how many arrangements of cards that could be a result of shuffling the initial deck she wins with Bob. We assume that all cards of the same colour are indistinguishable. Alice has recently heard about the Chinese remainder theorem, so it is sufficient for her to know the result modulo given prime number p.

Input Format

The first and only line of the standard input contains four integers r, b, k, and p (1 ≤ r, b ≤ 100,000, 1 ≤ k ≤ 10, 2 ≤ p ≤ 1,000,000,000) separated by single spaces. Number r denotes the number of red cards in the deck, whereas b - the number of black cards. p is a prime number.

Output Format

The first and only line of the standard output should contain the remainder of division by p of the number of arrangements of cards consisting of r red cards and b black cards, for which Alice wins the game.

Example

Input

4 2 1 17

Output

6

Notes

In this case Alice wins if either the first card is black or some sequence of consecutive black cards is immediately preceded by a smaller number of consecutive red cards. Let Rdenote a red card, and B - a black card. These are the arrangements of cards for which Alice wins (the first lecodeer in each of them denotes the card from the top of the deck): BBRRRR, BRBRRR, BRRBRR,BRRRBR, BRRRRB, and RBBRRR.