Problem G
Ball Tricks

RB is a basketball coach and he has several teams of exceptionally skilled basketball players, who dominate basketball leagues all over the world.

Why are RB’s players so good? The reason is that each of them has already mastered exactly one ball trick – either the Triple Spin, or the Power Charge. For convenience, we call the former trick 1 and the latter trick 2. These two tricks are extremely effective in attack.

Besides mastering such powerful trick, each of them also knows how to defend against exactly one ball trick. Therefore, one of their popular training routines is to let two players play against each other, one using a trick and the other trying to defend against it. We call this a move. The one who uses a trick is called an attacker, and the other is called a defender.

RB’s team can perform sequences of moves. To state it more concisely, we use the notation $(\text {Attacker}, \text {Defender})$ to represent a move. Suppose the current move is $(\texttt{A}, \texttt{B})$. A performs the only trick he knows.

• If A attacks successfully (i.e., B fails to defend), the next move will normally be $(\texttt{A}, \texttt{C})$ for some other player C.

• However, if it is the third consecutive time A attacks successfully, A will have to take a rest for the next two moves and the next move will be $(\texttt{C}, \texttt{D})$ for some other players C and D.

• If A fails (i.e., B defends successfully), the next move will be $(\texttt{B}, \texttt{C})$ for some other player C.

Note that in all cases, A, B, C, and D must be pairwise distinct players. In addition, C and D must not be at rest for the next move.

Today, RB inspects the team training. He is interested in sequences of moves of length exactly $N$. How many different sequences of moves of length $N$ are there? Two sequences of moves

and

are considered different if and only if for some $i$, $\mathrm{ATK}_ i \neq \mathrm{ATK}_ i^{'}$ or $\mathrm{DEF}_ i \neq \mathrm{DEF}_ i^{'}$.

Since the number may be too large, output it modulo $1\, 000\, 000\, 007$ ($10^9 + 7$).

Input

The first and only line of input consists of five non-negative integers, $a_{11}$, $a_{12}$, $a_{21}$, $a_{22}$, and $N$. $a_{ij}$ denotes the number of players in RB’s team who knows how to perform skill $i$ and how to defend against skill $j$.

For all test cases, $1 \leq a_{11} + a_{12} + a_{21} + a_{22} \leq 5\, 000$, $1 \leq N \leq 10^{18}$.

Output

Output the number of length-$N$ sequences of moves, modulo $1\, 000\, 000\, 007$.

Explanation

For Sample case 1, let $A$, $B$, $C$ be the players. Then valid sequences include:

• $((A, B), (B, C), (C, A))$

• $((A, C), (C, B), (B, A))$

• $((B, A), (A, C), (C, B))$

• $((B, C), (C, A), (A, B))$

• $((C, A), (A, B), (B, C))$

• $((C, B), (B, A), (A, C))$

For Sample case 2, let $A, B, C$ be the players, where $A$ is the player who can defend against skill 1. Then valid sequences include:

• $((B, C), (B, A), (A, C), (A, B), (A, C))$

• $((C, B), (C, A), (A, B), (A, C), (A, B))$

3 0 0 0 3

6

1 2 0 0 5

2

1 2 0 0 4

4

1 2 0 0 6

0

369 777 2000 913 123456789012345678

460130848