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: t, *n = map(int, open(0))
  for k in n:
      print(
          sum(
              [
                  k**j
                  * [
                      0,
                      765144583,
                      346175634,
                      347662323,
                      5655049,
                      184117322,
                      927321758,
                      444014759,
                      542573865,
                      237315285,
                      417297686,
                      471090892,
                      183023413,
                      660103155,
                      727008098,
                      869418286,
                      539588932,
                      729548371,
                      700407153,
                      404391958,
                      962779130,
                      184117322,
                      927321758,
                      444014759,
                      542573865,
                      237315285,
                      417297686,
                      471090892,
                      183023413,
                      660103155,
                      727008098,
                      869418286,
                  ][(k & 1 << 4) + j]
                  for j in range(16)
              ]
          )
          % (10**9 + 7)
      )
  
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)."}]