该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述：

喵喵刚刚在学习斐波那契数列。斐波那契数列是一个非常著名的数字序列，由 $1,1,2,3,5,8,13,21,34,......$ 组成。斐波那契数列的第 $i$ 项称为 $F_i$。

数列中的下一个数是由前两个数相加得到的，例如

• $F_1 = 1$
• $F_2 = 1$
• $F_3 = F_1 + F_2 = 1 + 1 = 2$
• $F_4 = F_2 + F_3 = 1 + 2 = 3$
• ...

因此，序列是由前两个项 $F_1$ 和 $F_2$ 决定的，所有其他项都是在这两个项的基础上计算出来的。

喵喵想发明自己的数列，并将其称为喵喵数列。他想知道，如果使用相同的结构，但使用不同的 $F_1$ 和 $F_2$ 会发生什么情况，例如，如果 $F_1 = 3$，$F_2 = 4$，在这种情况下，数列将为：$3, 4, 7, 11, 18, 29, ...$。

帮助喵喵试验不同的初始值，以便他能选择理想的喵喵数列。马可会问你 $Q$ 个问题，在每个问题中，他会给出序列的两个初始值 $A$ 和 $B$，并要求你计算 $i$ 项的值。

输入：

第一行输入一个正整数 $Q$

接下来 $Q$ 行每行输入三个整数 $A,B,i$

• $0 \le A, B \le 10^6$
• $1 \le Q \le 10^5$
• $1 \le i \le 10^6$

输出：

输出共 $Q$ 行，每个问题一行，包含一个整数，代表所询问的项对 $10^9 + 7$ 的模数

样例输入1:

5
1 1 9
3 4 1
5 10 2
3 4 6
7 3 7585

样例输出1：

34
3
10
29
814888492

提示：