Problem 1935: Area Under Path

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

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