Sadə Təkrarlanma

Qəhrəmanımız bir həftədir ki, bir araşdırma üzərində işləyir və bu araşdırmanın bir hissəsini həll etmək üçün yaxınlarda bir təkrarlanan əlaqə əldə edib. Amma onun vaxtı yoxdur. Siz kömək edə bilərsinizmi?

Təkrarlanan əlaqə aşağıdakı kimidir:

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

Sizə f(1), f(0), g(1), g(0) başlanğıc qiymətləri verilir. Siz f(n) mod 10^9 hesablamalısınız.

Giriş

Birinci sətirdə sizə 4 ədəd verilir: f(1), f(0), g(1), g(0) (1 ≤ f(0), f(1), g(0), g(1) ≤ 10) müvafiq olaraq. Növbəti sətirdə sizə tam ədəd n (1 ≤ n ≤ 10^18) verilir.

Çıxış

f(n) mod 10^9 hesablayın.