题目描述

点此下载 2024 年实验室二面题解

你是我的世界高手，你想要计算一个递推公式为$F_{n}=F_{n-1}+F_{n-2}$的数列的无穷项，于是你决定创造一台红石计算机。你的同学是数学高手，现在他给你一些资料：

1. $2×2$矩阵与$2×1$矩阵乘法法则为$\left[\begin{matrix}a_{11} & a_{12} \\ a_{21} & a_{22} \end{matrix}\right]*\left[\begin{matrix} b_{11}\\b_{12} \end{matrix}\right]= \left[\begin{matrix}a_{11}*b_{11}+a_{12}*b_{12} \\ a_{21}*b_{11}+a_{22}*b_{12} \end{matrix}\right],$例如$\left[\begin{matrix}0 & 1 \\ 1 & 1 \end{matrix}\right]*\left[\begin{matrix} F_{n-1}\\F_{n-2} \end{matrix}\right]= \left[\begin{matrix} F_{n-1} \\ F_{n-1}+F_{n-2} \end{matrix}\right];$

2.$2×2$矩阵与$2×2$矩阵乘法法则为$\left[\begin{matrix}a_{11} & a_{12} \\ a_{21} & a_{22} \end{matrix}\right]*\left[\begin{matrix}b_{11} & b_{12} \\ b_{21} & b_{22} \end{matrix}\right]= \left[\begin{matrix}a_{11}*b_{11}+a_{12}*b_{21}&a_{11}*b_{12}+a_{12}*b_{22}\\ a_{21}*b_{11}+a_{22}*b_{21} & a_{21}*b_{12}+a_{22}*b_{22}\end{matrix}\right]$ ，例如 $\left[\begin{matrix}0 & 1 \\ 1 & 1 \end{matrix}\right]^{2}= \left[\begin{matrix} 1 & 1 \\ 1 & 2 \end{matrix}\right]$；

3. 矩阵乘法满足结合律$;$

给定该数列的前两项(第1项和第2项)，请你计算出第$n$项的值，由于结果很大，请你将结果对$1e9+7$取模；

输入描述

第一行输入一个整数$T$表示有$T$组测试数据。

接下来每组测试数据输入三个整数$a,b,n$分别表示该数列前两项和项数。

$1<=T<=1e4,1<=a,b<=100,3<=n<=1e18$

输出描述

输出$T$行，每行一个整数代表答案。

示例 1

输入

1
3 4 17

输出

5778