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 = int(input())
  mod = 10**9 + 7
  for case in range(T):
      n = int(input())
      k = n // 2
      ans = (
          (
              (k + 1)
              * (k + 2)
              * (k + 3)
              * (k + 4)
              * (k + 5)
              * (
                  -50050 * n**9 * k
                  + 386100 * n**8 * k**2
                  - 2413125 * n**8 * k
                  - 1801800 * n**7 * k**3
                  + 16216200 * n**7 * k**2
                  - 49849800 * n**7 * k
                  + 5605600 * n**6 * k**4
                  - 65165100 * n**6 * k**3
                  + 285985700 * n**6 * k**2
                  - 576425850 * n**6 * k
                  - 12108096 * n**5 * k**5
                  + 171531360 * n**5 * k**4
                  - 966125160 * n**5 * k**3
                  + 2749546800 * n**5 * k**2
                  - 4088037954 * n**5 * k
                  + 18345600 * n**4 * k**6
                  - 305454240 * n**4 * k**5
                  + 2086302400 * n**4 * k**4
                  - 7557336150 * n**4 * k**3
                  + 15640447550 * n**4 * k**2
                  - 18305945385 * n**4 * k
                  - 19219200 * n**3 * k**7
                  + 366912000 * n**3 * k**6
                  - 2934072960 * n**3 * k**5
                  + 12806757600 * n**3 * k**4
                  - 33368162100 * n**3 * k**3
                  + 53348049300 * n**3 * k**2
                  - 51266409740 * n**3 * k
                  + 13305600 * n**2 * k**8
                  - 286070400 * n**2 * k**7
                  + 2614953600 * n**2 * k**6
                  - 13296679200 * n**2 * k**5
                  + 41391926800 * n**2 * k**4
                  - 82078221750 * n**2 * k**3
                  + 105034352450 * n**2 * k**2
                  - 85482724200 * n**2 * k
                  - 5491200 * n * k**9
                  + 131155200 * n * k**8
                  - 1346822400 * n * k**7
                  + 7797283200 * n * k**6
                  - 28086983904 * n * k**5
                  + 65754247440 * n * k**4
                  - 102157331940 * n * k**3
                  + 106855669500 * n * k**2
                  - 75640798296 * n * k
                  + 1025024 * k**10
                  - 26906880 * k**9
                  + 306324480 * k**8
                  - 1985860800 * k**7
                  + 8100701952 * k**6
                  - 21735549360 * k**5
                  + 39163472320 * k**4
                  - 48125918400 * k**3
                  + 41580305424 * k**2
                  - 26358665760 * k
                  + 3003 * n**10
                  + 165165 * n**9
                  + 3963960 * n**8
                  + 54504450 * n**7
                  + 473792319 * n**6
                  + 2708871165 * n**5
                  + 10261040790 * n**4
                  + 25253728500 * n**3
                  + 38298988728 * n**2
                  + 31917805920 * n
                  + 10897286400
              )
          )
          % mod
      ) * pow(1307674368000, mod - 2, mod)
      ans %= mod
      print(ans)
  
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)."}]