output_description: Print T lines. The i-th line should contain the answer to the i-th test case.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      T
      \mathrm{case}_1
      \vdots
      \mathrm{case}_T
      
  
  Each case is given in the following format:
  
      
      
      N
attempt: import sys
  import numpy as np
  
  read = sys.stdin.buffer.read
  readline = sys.stdin.buffer.readline
  readlines = sys.stdin.buffer.readlines
  
  MOD = 10**9 + 7
  
  
  def fft_convolve(f, g):
      """
      数列 (多項式) f, g の畳み込みの計算．上下 15 bitずつ分けて計算することで，
      30 bit以下の整数，長さ 250000 程度の数列での計算が正確に行える．
      """
      Lf, Lg = f.shape[-1], g.shape[-1]
      Lg = g.shape[-1]
      L = Lf + Lg - 1
      fft_len = 1 << L.bit_length()
      fh, fl = f >> 15, f & (1 << 15) - 1
      gh, gl = g >> 15, g & (1 << 15) - 1
  
      def conv(f, g):
          Ff = np.fft.rfft(f, fft_len)
          Fg = np.fft.rfft(g, fft_len)
          h = np.fft.irfft(Ff * Fg)
          return np.rint(h)[..., :L].astype(np.int64) % MOD
  
      x = conv(fl, gl)
      z = conv(fh, gh)
      y = conv(fl + fh, gl + gh) - x - z
      return (x + (y << 15) + (z << 30)) % MOD
  
  
  def coef_of_generating_function(P, Q, N):
      """compute the coefficient [x^N] P/Q of rational power series.
  
      Parameters
      ----------
      P : np.ndarray
          numerator.
      Q : np.ndarray
          denominator
          Q[0] == 1 and len(Q) == len(P) + 1 is assumed.
      N : int
          The coefficient to compute.
      """
      assert Q[0] == 1 and len(Q) == len(P) + 1
  
      def convolve(f, g):
          return fft_convolve(f, g)
  
      while N:
          Q1 = np.empty_like(Q)
          Q1[::2] = Q[::2]
          Q1[1::2] = MOD - Q[1::2]
          P = convolve(P, Q1)[N & 1 :: 2]
          Q = convolve(Q, Q1)[::2]
          N >>= 1
      return P[0]
  
  
  den = np.array([1, -1], np.int64)
  for _ in range(5):
      den = np.convolve(den, np.array([1, -2, 0, 2, -1]))
  
  num = np.zeros_like(den)[:-1]
  num[5] = 1
  
  
  def f(N):
      return coef_of_generating_function(num, den, N)
  
  
  T = int(readline())
  nums = map(int, read().split())
  for n in nums:
      print(f(n))
  
problem_description: Statement
  
  Given is an integer N. Snuke will choose integers s_1, s_2, n_1, n_2, u_1,
  u_2, k_1, k_2, e_1, and e_2 so that all of the following six conditions will
  be satisfied:
  
    * 0 \leq s_1 < s_2
    * 0 \leq n_1 < n_2
    * 0 \leq u_1 < u_2
    * 0 \leq k_1 < k_2
    * 0 \leq e_1 < e_2
    * s_1 + s_2 + n_1 + n_2 + u_1 + u_2 + k_1 + k_2 + e_1 + e_2 \leq N
  
  For every possible choice (s_1,s_2,n_1,n_2,u_1,u_2,k_1,k_2,e_1,e_2), compute
  (s_2 − s_1)(n_2 − n_1)(u_2 − u_1)(k_2 - k_1)(e_2 - e_1), and find the sum of
  all computed values, modulo (10^{9} +7).
  
  Solve this problem for each of the T test cases given.
samples: [{"input": "4\n    4\n    6\n    10\n    1000000000", "output": "0\n    11\n    4598\n    257255556\n    \n\n  * When N=4, there is no possible choice (s_1,s_2,n_1,n_2,u_1,u_2,k_1,k_2,e_1,e_2). Thus, the answer is 0.\n  * When N=6, there are six possible choices (s_1,s_2,n_1,n_2,u_1,u_2,k_1,k_2,e_1,e_2) as follows:\n    * (0,1,0,1,0,1,0,1,0,1)\n    * (0,2,0,1,0,1,0,1,0,1)\n    * (0,1,0,2,0,1,0,1,0,1)\n    * (0,1,0,1,0,2,0,1,0,1)\n    * (0,1,0,1,0,1,0,2,0,1)\n    * (0,1,0,1,0,1,0,1,0,2)\n  * We have one choice where (s_2 \u2212 s_1)(n_2 \u2212 n_1)(u_2 \u2212 u_1)(k_2 - k_1)(e_2 - e_1) is 1 and five choices where (s_2 \u2212 s_1)(n_2 \u2212 n_1)(u_2 \u2212 u_1)(k_2 - k_1)(e_2 - e_1) is 2, so the answer is 11.\n  * Be sure to find the sum modulo (10^{9} +7)."}]