Просте рекурентне співвідношення

Наш герой працював над дослідженням протягом тижня і нещодавно отримав рекурентне співвідношення для вирішення частини цього дослідження. Але у нього немає часу. Чи могли б ви допомогти?

Рекурентне співвідношення має вигляд:

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.

Приклади