时间限制： 1.0 秒

空间限制： 512 MB

题目描述

定义 Fibonacci 数列：

$$fib(n) = \begin{cases} 0, & n = 0 \\ 1, & n = 1 \\ fib(n - 1) + fib(n - 2), & n \ge 2 \end{cases} $$

给定正整数 $n$，求 $fib(n) \bmod {10^9 + 7}$ 的值。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 $T$，表示共有 $T$ 组数据。

接下来 $T$ 行，每组数据占一行，分别包含一个正整数 $n$。

输出格式

输出到标准输出。

共输出 $T$ 行，第 $i$ 行对应第 $i$ 组询问所求的答案。

2
10
1000

55
517691607

子任务

对于所有数据，保证 $T=200, n\le 10^{18}$。

提示

Chap 01 绪论，Fibonacci 数，习题 [1-20] (b)。

结合习题 [1-14] power2() 和矩阵乘法设计对应的算法。