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取模

Input Format

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

Output Format

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

Sample

样例输入

2
4
11

样例输出

11
139801

Hint

$1 \leq t \leq 2000$

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