Peter is standing at the origin of the Cartesian plane, and he decided to take a *regular* walk to point $(N, M)$ for some positive integers $N$ and $M$.

In each step of a *regular* walk, Peter must move parallel to one of the axes. During a move, he can go either one unit to the right or one unit up.

Formally, a regular walk from $(0, 0)$ to $(N, M)$ is a sequence of points $(x_i, y_i)\ (0 \leq i \leq N + M)$ such that:

- $(x_0, y_0) = (0, 0)$ and $(x_{N+M}, y_{N+M}) = (N, M)$, and
- for each $i = 1, \dots, N+M$, either $(x_i, y_i) = (x_{i-1} + 1, y_{i-1})$ or $(x_i, y_i) = (x_{i-1}, y_{i-1} + 1)$.

We define the area under a regular walk as the area of the polygon whose vertices in clockwise order are $(0, 0) = (x_0, y_0), (x_1, y_1), \dots, (x_{N+M}, y_{N+M}) = (N, M)$ and $(N, 0)$.

Given a prime number $P$ and a remainder $R$, you have to find the number $W$ of *regular* walks from $(0, 0)$ to $(N, M)$ under which the area is congruent to $R$ modulo $P$. Since the answer can be very large, you have to compute it modulo $10^9 + 7$.

## Input data

The input file consists of a single line containing integers $N$, $M$, $P$, $R$.

## Output data

The output file must contain a single line consisting of integer $W$.

## Constraints and clarifications

- $1 \leq N, M \leq 10^6$.
- $1 \leq P \leq 100$.
- $0 \leq R < P$.
- $P$ is a prime number.
- For tests worth $16$ points, $N, M \leq 10$.
- For tests worth $11$ more points, $N, M \leq 100$.
- For tests worth $28$ more points, $N \equiv M \equiv 0 \pmod{P}$.

## Example 1

`stdin`

```
2 2 3 1
```

`stdout`

```
2
```

## Explanation

In the **first sample case**, there are six possible *regular* walks from $(0, 0)$ to $(N, M)$, as shown in the figure below.

The area under the second and the sixth paths are $1$ and $4$ respectively, both of which give a remainder of $1$ when divided by $3$.

## Example 2

`stdin`

```
2 7 5 3
```

`stdout`

```
7
```