Простая рекурсия

Наш герой всю неделю занимался исследованием и недавно вывел рекуррентное соотношение для решения одной из его задач. Однако у него нет времени на его решение. Можете помочь?

Рекуррентное соотношение имеет следующий вид:

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

Вам даны начальные значения f(1), f(0), g(1), g(0). Необходимо вычислить f(n) по модулю 10^9.

Входные данные

Первая строка содержит 4 числа: f(1), f(0), g(1), g(0) (1 ≤ f(0), f(1), g(0), g(1) ≤ 10). В следующей строке дано целое число n (1 ≤ n ≤ 10^18).

Выходные данные

Выведите f(n) mod 10^9.

Примеры