Masala #1047

Xotira 32 MB Vaqt 1000 ms
14

Is it Fibonacci?

Barchasi juda oddiy. Uchta butun \(x,y,a\) sonlari beriladi.

\(f(n) = \begin{cases} x & n = 0 \\ y & n = 1 \\ f(n-1)+f(n-2) & n \ge 2 \end{cases}\)

bo`lsa, \(f(a)\) ni \(10^9+7\) ga bo`lgandagi qoldig`ini hisoblang.


Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son - \(T(1 \leq T \leq 2*10^5)\) testlar soni kiritiladi.

Har keyingi yangi qatorda, yangi test uchun - \(x,y(0 \leq x,y \leq 10^9)\) va \(a(0 \leq a \leq 2*10^5)\) sonlari kiritiladi.


Chiquvchi ma'lumotlar:

Har bir test uchun yangi qatorda bittadan butun son, masala javobini chiqaring.


Misollar
# input.txt output.txt
1
11
3 5 2
1 1 6
6 7 1
1 1 12
7 4 5
5 6 9
3 2 0
1 1 40
2 2 19
19 75 6
976 85 12
8
13
7
233
41
309
3
165580141
13530
695
99104
Izoh:

Python tili uchun PyPy kompilyatoridan foydalanishni maslahat beramiz!