C. Isolation
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Maria had a big fight with Kazuki and now wants to avoid him at all costs. Currently, Kazuki is at $$$(0, 0)$$$ in the coordinate plane, while Maria is at $$$(X, Y)$$$.

Maria wants to take a walk while maintaining a Manhattan distance strictly larger than $$$D$$$ from Kazuki, i.e. if her current coordinates is $$$(x, y)$$$, then $$$|x| + |y| \gt D$$$ must hold. Every second, she must choose one of the four cardinal directions (up, down, left, right) and move $$$1$$$ unit in that direction.

How many ways are there for her to take a walk without ever getting too close to Kazuki for $$$N$$$ seconds? Since the answer may be too large, print the answer modulo $$$10^{9} + 7$$$.

Input

The first and only line of input contains four space-separated integers, denoting $$$X, Y, N, D$$$ ($$$|X|, |Y| \le 1500, |X| + |Y| \gt D, 1 \le N \le 1500, 0 \le D \le 4$$$) respectively.

Output

Output a single integer, the number of ways for Maria to take a walk while keeping a distance from Kazuki for $$$N$$$ seconds, modulo $$$10^{9} + 7$$$.

Scoring

Subtask 1 (9 points): $$$N \le 9$$$

Subtask 2 (17 points): $$$N \le 100$$$

Subtask 3 (25 points): $$$D=0$$$

Subtask 4 (49 points): No additional constraints

Examples
Input
1 -1 2 1
Output
8
Input
6 2 18 0
Output
998199851
Input
1 4 9 4
Output
73340
Note

The following $$$8$$$ walks are valid for sample $$$1$$$:

$$$(1, -1) \rightarrow (1, -2) \rightarrow (1, -3)$$$

$$$(1, -1) \rightarrow (1, -2) \rightarrow (1, -1)$$$

$$$(1, -1) \rightarrow (1, -2) \rightarrow (2, -2)$$$

$$$(1, -1) \rightarrow (1, -2) \rightarrow (0, -2)$$$

$$$(1, -1) \rightarrow (2, -1) \rightarrow (3, -1)$$$

$$$(1, -1) \rightarrow (2, -1) \rightarrow (2, 0)$$$

$$$(1, -1) \rightarrow (2, -1) \rightarrow (2, -2)$$$

$$$(1, -1) \rightarrow (2, -1) \rightarrow (1, -1)$$$

On the other hand, the path $$$(1, -1) \rightarrow (0, -1) \rightarrow (0, -2)$$$ is invalid as the Manhattan distance between Maria's position and Kazuki's position is $$$1 \le D$$$ after $$$1$$$ second.