Жууху дараах нөхцлийг хангасан нэгэн төрлийн дараалал зохиосон:

Танд $x$ ба $y$ тоо өгөгдөнө. $f_{n}$-ийг $1000000007$ $(10^{9} + 7)$-д хуваасан үлдэгдлийг тооцоолно уу.

Оролт

Эхний мөрөнд хоёр бүхэл $x$ ба $y$ $(|x|, |y| ≤ 10^{9})$ тоонууд агуулагдана. Хоёр дахь мөрөнд нэг бүхэл $n$ $(1 ≤ n ≤ 2*10^{9})$ тоо агуулагдана.

Гаралт

$f_{n}$-ийг $1000000007$ $(10^{9} + 7)$-д хуваасан үлдэгдлийг хэвлэнэ.

Эхний жишээнд $f_{2} = f_{1} + f_{3}$, $3 = 2 + f_{3}$, $f_{3} = 1$ байна.

Хоёр дахь жишээнд $f_{2} =  - 1$; $ - 1$-ийн $(10^{9} + 7)$-д хуваасан үлдэгдэл нь $(10^{9} + 6)$-тай тэнцүү байна.