故事背景

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

题目描述

大家都知道，斐波那契数列的前两项是1 1或1 2，其他每项的数都等于前两个数的和。你作为斐波那契，想改变这个数列前两项的值变成$a$和$b$，请你求出这个斐波那契数列的第$k$项的值$mod$ $10^9+7$是多少。

格式

输入

多组样例。

第一行为整数$t$，表示$t$组样例。

接下来$t$行，每行三个整数$a, b, k$。

输出

输出$t$行，每行为第$i$组样例的答案。

样例

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

提示

$1 \leq t \leq 100$

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

$1 \leq k \leq 100$