B. Жууху ба дарааллууд

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

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

Танд $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)$-д хуваасан үлдэгдлийг хэвлэнэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
2 3
3
Гаралт
1
Оролт
0 -1
2
Гаралт
1000000006

Тэмдэглэл

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

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

Сэтгэгдлүүдийг ачааллаж байна...