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 10^9.
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 ≤ 10^18).
Output f(N) mod 10^9.