Simple Recurrence#7251
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 \cdot f(n - 1) + 2 \cdot f(n - 2) + 2 \cdot g(n - 1) + 3 \cdot g(n - 2),
g(n) = g(n - 1) + 2 \cdot g(n - 2).
You are given the initial value of , , , . You have to output modulo 10^9.
In the first line you are given numbers: , , , (1 \leq f(0), f(1), g(0), g(1) \leq 10) respectively. In the next line you are given an integer (1 \leq n \leq 10^{18}).
Output mod 10^9.
Example 1