Little T has recently been learning how to trade stocks, and he has received insider information: the stock of Company F is going to skyrocket.

The stock price each day is known to be a positive integer, and due to objective reasons, it can be at most $N$. During the $K$ days of the skyrocketing period, Little T observed that: except for the first day, the stock price each day is higher than the previous day, and the increase (the difference between the current day's price and the previous day's price) does not exceed $M$, where $M$ is a positive integer. These parameters satisfy $M(K-1) < N$.

Little T has forgotten the specific stock price for each of these $K$ days. He now wants to know how many possible sequences of stock prices there are for these $K$ days.

Input

The input consists of a single line containing four space-separated integers: $N$, $K$, $M$, and $P$. For an explanation of $P$, see the "Output" section below.

Output

Output a single integer representing the number of possible stock price sequences for these $K$ days, modulo $P$.

Examples

Input 1

7 3 2 997

Output 1

16

Note 1

The output 16 indicates that there are 16 possible sequences of stock prices for the input example:

• {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {1, 3, 5},
• {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {2, 4, 6},
• {3, 4, 5}, {3, 4, 6}, {3, 5, 6}, {3, 5, 7},
• {4, 5, 6}, {4, 5, 7}, {4, 6, 7}, {5, 6, 7}.

Subtasks

It is guaranteed that for $20\%$ of the data, $M, N, K, P \le 20000$. For $100\%$ of the data, $M, K, P \le 10^9$ and $N \le 10^{18}$.