已知一个数列的通向公式：F[n] = 2F[n - 1] + 4F[n - 2] + 2F[n - 3]，F[1]、F[2]、F[3]均为1。输入n（1 <= n <= 10^18），求F[n]的值。因为数太大，输出对1000000007取模的值。
第一行输入T，表示T组数据，接下来T行，每行一个n，1 <= n <= 10^18。
3 3 6 100
1 78 360461226