Problem statement

You have three types of balls:

• $R$ red balls
• $G$ green balls
• $B$ blue balls

You must arrange all $R+G+B$ balls in a single row. For each prefix of the row of length $i$ ( where $1 \leq i \leq R+G+B$ ), let

• $r_i=$ number of red balls in the first $i$ positions,
• $g_i=$ number of green balls in the first $i$ positions,
• $b_i=$ number of blue balls in the first $i$ positions.

You are given an integer $t$ which represents a type of condition your arrangement need to satisfy for every prefix length $i$:

• if $t=0$ then $r_i \leq g_i + K$
• if $t=1$ then $g_i \leq b_i + K$
• if $t=2$ then $b_i \leq r_i + K$

Here $t, K$ are given non-negative integers.

Task: Compute the number of distinct arrangements of the $R$ red, $G$ green, and $B$ blue balls that satisfy that prefix constraints.

Input

• Five integers: $R, G, B, t, K$.

Output

• A single integer: The total number of valid arrangements $(\bmod 10^9 + 7)$.

Sample Input

3 3 3 0 3

Sample Output

1680

Constraints

• $0 \leq R, G, B, K \leq 10^6$
• $0 \leq t \leq 2$