Our hero has been working on a research for a week. And he has recently gotten a recurrence relation for solving a part of that research. But he has no time. Could you do it?

Recurrence relation is as follows:

f(n) = 3 * f(n - 1) + 2 * f(n - 2) + 2 * g(n - 1) + 3 * g(n - 2),

g(n) = g(n - 1) + 2 * g(n - 2).

You are given the initial value of f(1), f(0), g(1), g(0). You have to output f(n) modulo 109.

Input

In the first line you are given 4 numbers: f(1), f(0), g(1), g(0) (1 ≤ f(0), f(1), g(0), g(1) ≤ 10) respectively. In the next line you are given an integer n (1 ≤ n ≤ 1018).

Output

Output f(n) mod 109.