H. marble的神秘数列

Type: Default

500ms

256MiB

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.

Problem Description

在二次元的奇幻世界中，隐藏着一个神秘的数列，它似乎拥有某种特殊的魔力。这个数列的前三项均为1，而之后的每一项都遵循着一个独特的规律。具体来说，对于数列的第 $n$ 项（ $n$ 大于等于4），它满足以下公式：

$$a_n = \begin{cases} 1 & n \leq 3 \\ 3 \times a_{n-1} + 2 \times a_{n-2} + 6 \times a_{n-3} & n > 3 \\ \end{cases}$$

在二次元世界中，有一个特别的日子——3月26日，它与这个数列似乎有着某种神秘的联系。传说在这一天，数列中的某一特定项将揭示出一个深藏的奥秘。

现在，marble——一位热爱二次元的探险家，决心揭开这个秘密。请你帮助marble编写一个程序，输入一个正整数 $n$ （ $n$ 大于等于4），输出数列的第 $n$ 项的值，由于这个数列很大请对1000000007取模

多组询问，第一行输入一个整数t代表询问数，后面 $t$ 行每行一个整数 $n$ 表示询问数列的第几项

共 $t$ 行每行一个整数表示答案

样例输入

2
4
11

样例输出

11
139801

$1 \leq t \leq 2000$

$1 \leq n \leq 10^{12}$