Area Under Path

Time limit: 0.5s Memory limit: 128MB Input: Output:

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

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)(0, 0) to (N,M)(N, M) is a sequence of points (xi,yi) (0iN+M)(x_i, y_i)\ (0 \leq i \leq N + M) such that:

  • (x0,y0)=(0,0)(x_0, y_0) = (0, 0) and (xN+M,yN+M)=(N,M)(x_{N+M}, y_{N+M}) = (N, M), and
  • for each i=1,,N+Mi = 1, \dots, N+M, either (xi,yi)=(xi1+1,yi1)(x_i, y_i) = (x_{i-1} + 1, y_{i-1}) or (xi,yi)=(xi1,yi1+1)(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)=(x0,y0),(x1,y1),,(xN+M,yN+M)=(N,M)(0, 0) = (x_0, y_0), (x_1, y_1), \dots, (x_{N+M}, y_{N+M}) = (N, M) and (N,0)(N, 0).

Given a prime number PP and a remainder RR, you have to find the number WW of regular walks from (0,0)(0, 0) to (N,M)(N, M) under which the area is congruent to RR modulo PP. Since the answer can be very large, you have to compute it modulo 109+710^9 + 7.

Input data

The input file consists of a single line containing integers NN, MM, PP, RR.

Output data

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

Constraints and clarifications

  • 1N,M1061 \leq N, M \leq 10^6.
  • 1P1001 \leq P \leq 100.
  • 0R<P0 \leq R < P.
  • PP is a prime number.
  • For tests worth 1616 points, N,M10N, M \leq 10.
  • For tests worth 1111 more points, N,M100N, M \leq 100.
  • For tests worth 2828 more points, NM0(modP)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)(0, 0) to (N,M)(N, M), as shown in the figure below.

The area under the second and the sixth paths are 11 and 44 respectively, both of which give a remainder of 11 when divided by 33.

Example 2

stdin

2 7 5 3

stdout

7

Log in or sign up to be able to send submissions!