#241. 斐波那契变形

斐波那契变形

故事背景

你变成了伟大的意大利数学家斐波那契,创造了著名的斐波那契数列。

题目描述

大家都知道,斐波那契数列的前两项是1 1或1 2,其他每项的数都等于前两个数的和。你作为斐波那契,想改变这个数列前两项的值变成aabb,请你求出这个斐波那契数列的第kk项的值modmod 109+710^9+7是多少。

格式

输入

多组样例。

第一行为整数tt,表示tt组样例。

接下来tt行,每行三个整数a,b,ka, b, k

输出

输出tt行,每行为第ii组样例的答案。

样例

1
1 1 3
2
13
45 51 55
1 45 4
21 69 14
43 82 19
11 15 98
37 73 1
21 26 9
23 37 45
40 95 77
45 59 17
11 59 60
61 84 25
1 91 99
879190071
91
19101
280559
533339510
37
819
922494927
432101042
85683
753124438
5642989
534972841

提示

1t1001 \leq t \leq 100

1ab1051 \leq a \leq b \leq 10^5

1k1001 \leq k \leq 100