Задачі
Simple Recurrence
Simple Recurrence
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:
\textbf{f}(\textbf{n}) = \textbf{3 }* \textbf{f}(\textbf{n }- \textbf{1}) + \textbf{2 }* \textbf{f}(\textbf{n }- \textbf{2}) + \textbf{2 }* \textbf{g}(\textbf{n }- \textbf{1}) + \textbf{3 }* \textbf{g}(\textbf{n }- \textbf{2}),
\textbf{g}(\textbf{n}) = \textbf{g}(\textbf{n} - \textbf{1}) + \textbf{2} * \textbf{g}(\textbf{n} - \textbf{2}).
You are given the initial value of \textbf{f}(\textbf{1}), \textbf{f}(\textbf{0}), \textbf{g}(\textbf{1}), \textbf{g}(\textbf{0}). You have to output f(N) modulo \textbf{10^9}.
\InputFile
In the first line you are given \textbf{4} numbers: \textbf{f}(\textbf{1}), \textbf{f}(\textbf{0}), \textbf{g}(\textbf{1}), \textbf{g}(\textbf{0}) (\textbf{1 }≤ \textbf{f}(\textbf{0}), \textbf{f}(\textbf{1}), \textbf{g}(\textbf{0}), \textbf{g}(\textbf{1}) ≤ \textbf{10}) respectively. In the next line you are given an integer \textbf{N }(\textbf{1 }≤ \textbf{N }≤ \textbf{10^18}).
\OutputFile
Output \textbf{f}(\textbf{N}) mod \textbf{10^9}.
Вхідні дані #1
1 1 1 1 4
Вихідні дані #1
162