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

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

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

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

Вам дано початкові значення $f(1)$, $f(0)$, $g(1)$, $g(0)$. Ви повинні обчислити $f(n)$ за модулем 10^9.