U23585.矩阵加速(数列)

普及+/提高

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

已知一个数列 aa,它满足:

ax={1x{1,2,3}ax1+ax3x4a_x= \begin{cases} 1 & x \in\{1,2,3\}\\ a_{x-1}+a_{x-3} & x \geq 4 \end{cases}

aa 数列的第 nn 项对 109+710^9+7 取余的值。

输入格式

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

以下 TT 行,每行一个正整数 nn

输出格式

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

输入输出样例

  • 输入#1

    3
    6
    8
    10

    输出#1

    4
    9
    19

说明/提示

  • 对于 30%30\% 的数据 n100n \leq 100
  • 对于 60%60\% 的数据 n2×107n \leq2 \times 10^7
  • 对于 100%100\% 的数据 1T1001 \leq T \leq 1001n2×1091 \leq n \leq 2 \times 10^9
首页