1043 - 数论:矩阵快速幂:矩阵加速

通过次数

4

提交次数

12

时间限制 : 1 秒
内存限制 : 256 MB

已知一个数列 a,它满足: a 数列的第 n 项对 10^9+7 取余的值。

输入

第一行一个整数 T,表示询问个数。

以下 T 行,每行一个正整数 n

输出

每行输出一个非负整数表示答案。

样例

输入

3
6
8
10

输出

4
9
19

提示

  • 对于 30\% 的数据 n \leq 100
  • 对于 60\% 的数据 n \leq2 \times 10^7
  • 对于 100\% 的数据 1 \leq T \leq 1001 \leq n \leq 2 \times 10^9