SP7487 FLIB - Flibonakki

定义序列 $G(n)$ 为： - 当 $n = 0$ 时，$G(0) = 0$； - 当 $n > 0$ 时，$G(n) = G(n-1) + f(4n-1)$。 其中，$f(i)$ 表示第 $i$ 个斐波那契数。现给定一个整数 $n$，需要计算 $G(n)$ 模 1000000007 的结果。

第一行输入一个整数 $t$，表示测试用例的数量（$t < 10^5$）。接下来的 $t$ 行，每行包含一个整数 $n$，表示一个测试用例（$0 \leq n < 10^9$）。

对于每个测试用例，输出 $G(n) \bmod 1000000007$。

- 测试用例数量 $t$ 满足 $t < 10^5$ - 每个 $n$ 的取值范围是 $0 \leq n < 10^9$ **本翻译由 AI 自动生成**