Masala #1047

Xotira 32 MB Vaqt 1000 ms

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!