The Computing Association is one of the many student clubs at Peking University.

Today is the club recruitment day. Keke and Rikka, as the organizers, plan to play some small games with the freshmen at the recruitment site (the Triangle).

Rikka estimates that a total of $n$ freshmen will come to the site to play games. However, Rikka does not know when each person will arrive, so she assumes that the arrival time of each person is a real number chosen uniformly at random from the interval $[0, m]$.

Rikka and Keke will play games with the freshmen. Because they have excellent crowd control skills, each game lasts exactly $k$ seconds. When a freshman arrives, if both Rikka and Keke are currently in a game, the freshman will leave the site. Otherwise, the freshman will choose one of them who is not currently in a game with equal probability and start a game with that person. Suppose a freshman arrives at time $T$ and starts a game with Keke; then Keke will be in a game state during the interval $[T, T+k)$, during which she cannot start a new game with any other player. At time $0$, neither Rikka nor Keke is in a game.

Keke does not want any freshman to leave the recruitment site because both she and Rikka are busy. She is curious about the probability that all freshmen successfully play a game. Since the expression for the answer may be very complex, you only need to output the result modulo a prime $p$.

Input

A single line containing four positive integers $n, m, k, p$.

Output

A single integer representing the result of the answer modulo $p$.

Specifically, if the simplest fraction form of the answer is $\frac{x}{y}$, you only need to output the result of $x \times y^{p-2} \bmod p$.

The problem setter guarantees that for all test cases, the denominator $y$ of the simplest fraction is coprime to $p$.

Examples

Input 1

2 9 8 1000000007

Output 1

1

Note 1

Since there are only two freshmen, regardless of when they arrive, Rikka and Keke will always have at least one person available. Therefore, in all cases, all freshmen successfully play a game.

Input 2

4 6 3 998244353

Output 2

873463809

Note 2

The answer is $\frac{1}{8}$.

Input 3

7 20 2 998244353

Output 3

591287283

Subtasks

For $10\%$ of the data, $n \le 3$.

For $20\%$ of the data, $n \le 4$.

For $35\%$ of the data, $n \le 6$.

For $50\%$ of the data, $n \le 10$.

For $60\%$ of the data, $n \le 15$.

For $70\%$ of the data, $n \le 25$.

For $80\%$ of the data, $n \le 35$.

For $90\%$ of the data, $n \le 45$.

For $100\%$ of the data, $n \le 50$.

For all test cases, $1 \le n \le 50, 1 \le k \le m \le 150, 10^8 < p \le 10^9+9$.