SP19406 FIBOSUM2 - Fibonacci extraction Sum

设 $fib[i]$ 为斐波那契数列第 $i$ 项。 给定三个整数 $c,k,n$，求 $$\sum ^{n} _ {i=1}{fib[k\times i+c]}$$ 对 $10 ^ 9 + 7$ 取模的值。

第一行一个非负整数 $T$，表示测试数据组数。 之后每行三个整数 $c,k,n$。

输出 $T$ 行，每行一个非负整数表示这组数据的答案。

- $ 0 < T \le 60606 $ - $ 0 \le c < k \le 2^{15} $ - $ 0 < N \le 10^{18} $