You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时间限制： 1.0 秒

空间限制： 512 MB

题目描述

定义 Fibonacci 数列：

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

输入格式

从标准输入读入数据。

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

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

输出格式

输出到标准输出。

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

2
10
1000

55
517691607

子任务

对于所有数据，保证 $T=10^5, n\le 10^6$。

提示

Chap 01 绪论，Fibonacci 数，线性递归策略。

暴力递归的复杂度为 $O(2^n)$，可以考虑对递归过程做记忆化搜索，或者使用动态规划递推。

此外，请注意 $T=10^5$ 的限制，单次运算复杂度 $O(n)$ 的算法无法通过。但是你可以将所有对应的答案进行记忆化。