题目来自第 0 次 CSP 认证 T4，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 1.0 秒

空间限制： 256 MB

题目描述

我们把一个数称为有趣的，当且仅当：

1. 它的数字只包含 $0,1,2,3$，且这四个数字都出现过至少一次。
2. 所有的 $0$ 都出现在所有的 $1$ 之前，而所有的 $2$ 都出现在所有的 $3$ 之前。
3. 最高位数字不为 $0$。

因此，符合我们定义的最小的有趣的数是 $2013$。除此之外，$4$ 位的有趣的数还有两个：$2031$ 和 $2301$。

请计算恰好有 $n$ 位的有趣的数的个数。由于答案可能非常大，只需要输出答案除以 $10^9+7$ 的余数。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 $T$，表示共有 $T$ 组数据。

接下来 $T$ 行，每组数据占一行，分别包含一个正整数 $n$。

输出格式

输出到标准输出。

共输出 $T$ 行，每行一个整数，对应询问所求的答案，为恰好 $n$ 位整数中有趣的数的个数除以 $10^9+7$ 的余数。

2
4
100

3
929078566

数据范围

对于所有数据，$1\le T\le 100,~1\le n\le 1000$。