Zadanie

Fibonači

Počet bodov: 35

Fibonačiho postupnosť určite poznáte. Prvé dve čísla sú jednotky, a každé ďalše je súčet predošlích dvoch. Ale napadlo vás niekedy, ako by vyzerala, keby prvé dve čísla neboli jednotky? Alebo keby to nebol len súčet predošlích dvoch, ale ešte o \(1\) viac?

Miška to napadlo, a ako tak hútal, vyhútal takúto postupnosť: \[a_n = a_{n-1}+b_{n-2}-1\] Pýtate sa čo je \(b_n\)? No predsa postupnosť ktorú vyhútal Miško ešte o chvíľu skôr. Tá vyzerá takto: \[b_n = 2\cdot a_n+b_{n-2}+4\] Áno. Miško myslel dopredu, a vedel že postupnosť \(a_n\) ešte len vymyslí, a už ju použil.

Vždy keď sa Miško ale snaži vyrátať nejaký \(n\)-tý člen, niekde sa popletie.

Vstup a výstup

V jedinom riadku vstupu je \(5\) čísel \(a_0\), \(a_1\), \(b_0\), \(b_1\), \(n\) - prvé dva členy postupnosti \(a\), prvé dva členy postupnosti \(b\), a číslo \(n\).

Vypíšte na výstup \(a_n\) – \(n\)-té číslo postupnosti \(a\), tak ako je definovaná vyššie. Keďže toto číslo môže byť veľmi veľké, vypíšte jeho zvyšok po delení \(100\,000\,009\)¹. Vo všetkých vstupoch platí \(0\leq a_0, a_1, b_0, b_1\leq 100\).

V jednotlivích sadách je \(n\) najviac postupne \(10\), \(10^2\), \(10^3\), \(10^5\), \(10^6\).

Ak riešite úlohu v pythone, je možné, že budete potrebovať príkaz sys.setrecursionlimit(10**9).

Príklady

Input:

0 1 1 5 2

Output:

1

\(a_2 = a_1+b_0-1\) čiže 1+1-1.

Input:

3 9 8 2 5

Output:

99