B. RGB plants

Farmer John has recently bought three flowers in order to plant them around his house. The flowers were of three different colors red, green and blue.

As we all know, the garden that surrounds farmer John's house is a magical garden. That means that if you plant a number of flowers in it on some day, then the number of flowers will increase in the next day.

The garden increases the number of flowers depending on the color of the flowers, that is, if you plant a red flower in a day, then it will turn into 6 flowers in the next day (1 red flower, 2 green flowers, and 3 blue flowers). If you plant a green flower in a day, then it will turn into 15flowers in the next day (4 red flowers, 5 green flowers, and 6 blue flowers). If you plant a blue flower in a day, then it will turn into 24flowers in the next day (7 red flowers, 8 green flowers, and 9 blue flowers).

As we have mentioned above, farmer John has three flowers (1 red flower, 1 green flower, and 1 blue flower), and he will plant them in his magical garden around his house, so the number of the flowers will increase over time. Farmer John knows that if he plants his three flowers in his magical garden, then the number of flowers will increase from day to day, so he wants to know the total number of flowers in his magical garden in the nth day.

Input

The first line of the input is the number of test cases T (1 ≤ T ≤ 103). Each test case consists of a single line containing a single integer n(1 ≤ n ≤ 109).

Output

For each test case, print a single line containing the total number of flowers in the magical garden in the nth day modulo 1000000007.

Example

input

Copy

output

Copy

题意：一红花一天产生1朵红花，2朵绿花，3朵蓝花；

一朵绿花一天产生4朵红花，5朵绿花，6朵蓝花；

一朵蓝花一天产生7朵红花，8朵绿花，9朵蓝花；

一开始红花、绿花、蓝花各一朵，问n天之后一共有多少多花，结果对1000000007取模

题解：一开始想递归................所以是矩阵快速幂

#include <iostream>
#include<string.h>
#include<stdio.h>
#define ll long long
using namespace std;
const ll mod = 1000000007;
struct mat//定义矩阵结构体
{
  ll m[3][3];
  mat()
  {
    memset(m, 0, sizeof(m));
  }
};
mat mul(mat &A, mat &B)
{
  mat C;
  for (int i = 0; i < 3; i++)
  {
    for (int j = 0; j < 3; j++)
    {
      for (int k = 0; k < 3; k++) 
      {
        C.m[i][j] = (C.m[i][j] + A.m[i][k] * B.m[k][j]) % mod;
      }
    }
  }
  return C;
}
mat pow(mat A, ll n)
{
  mat B;
  for(int i=0;i<3;i++)//初始化方阵
    B.m[i][i]=0;

  //初始被乘矩阵的初值
    B.m[0][0]=1;
    B.m[1][0]=1;
    B.m[2][0]=1;
    
  while (n)
  {
    if (n & 1)
      B = mul(A, B);//注意这里，矩阵的左乘和右乘是不一样的，对应的系数矩阵也不一样
    A = mul(A, A);
    n >>= 1;
  }
  return B;
}
int main()
{
  ll n,t;
  cin>>t;
  while (t--)
  {
    cin>>n;
    mat A;//矩阵A是系数矩阵（转移矩阵）
    A.m[0][0]=1;
    A.m[0][1]=4;
    A.m[0][2]=7;
    A.m[1][0]=2;
    A.m[1][1]=5;
    A.m[1][2]=8;
    A.m[2][0]=3;
    A.m[2][1]=6;
    A.m[2][2]=9;

    
    if(n==1)
    {
      printf("3
");
    }
    // else if(n==2)
    // {
    //   printf("45
");
    // }
    else
    {
      mat B = pow(A, n-1);
      ll ans=B.m[0][0]+B.m[1][0]+B.m[2][0];
      printf("%lld
",ans%mod);
    }
  }
  return 0;
}