Description

Xiao T is learning to buy stocks. He got insider information: the stock of company F will soar. The price each day is a positive integer, and due to objective reasons, it can be at most $N$. During the $K$ days of soaring, Xiao T observed that: except for the first day, each day's price is higher than the previous day, and the increase (i.e., today's price minus yesterday's price) does not exceed $M$, where $M$ is a positive integer. Moreover, these parameters satisfy $M(K-1) < N$. Xiao T forgot the exact price on each of the $K$ days; he now wants to know how many possible price sequences there are for these $K$ days.

Input Format

Only one line with four space-separated numbers: $N$, $K$, $M$, $P$. For $P$, see the explanation in the “Output Format” section below. It is guaranteed that for 20% of the testdata $M, N, K, P \le 20000$, and for 100% of the testdata $M, K, P \le 10^9$, $N \le 10^{18}$.

Output Format

Output a single number: the number of possible price sequences over $K$ days modulo $P$.

7 3 2 997

16

Hint

Sample Explanation
The output sample’s $16$ means there are $16$ possible price sequences for the input sample:

$\{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\}$.

Translated by ChatGPT 5