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}.