Problem:
 Score : 600 points    Problem 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.      Constraints  All values in input are integers.  1 \leq T \leq 100  1 \leq N \leq 10^{9}         Input 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       Output Print T lines. The i -th line should contain the answer to the i -th test case.        Sample Input 1 4
4
6
10
1000000000      Sample Output 1 0
11
4598
257255556   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 .  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:  (0,1,0,1,0,1,0,1,0,1)  (0,2,0,1,0,1,0,1,0,1)  (0,1,0,2,0,1,0,1,0,1)  (0,1,0,1,0,2,0,1,0,1)  (0,1,0,1,0,1,0,2,0,1)  (0,1,0,1,0,1,0,1,0,2)    We have one choice where (s_2 − s_1)(n_2 − n_1)(u_2 − u_1)(k_2 - k_1)(e_2 - e_1) is 1 and five choices where (s_2 − s_1)(n_2 − n_1)(u_2 − u_1)(k_2 - k_1)(e_2 - e_1) is 2 , so the answer is 11 .  Be sure to find the sum modulo (10^{9} +7) .

Solution (Python):
import numpy as np


def lagrange(DEG, MOD):
    DIV = 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 * 5 * 4 * 3 * 2 * 1

    def sub(n):
        result = 0
        for j in range(5, n + 1):
            tmp = 1
            for i in range(9):
                tmp *= j + 4 - i
            for i in range(5):
                tmp *= 5 + (n - j) // 2 - i
            tmp //= DIV
            result += tmp
        return result

    def np_pow(arr, exp, mod):
        res = np.ones_like(arr)
        tmp = arr.copy()
        while exp:
            if exp & 1:
                res = res * tmp % mod
            tmp = tmp * tmp % mod
            exp >>= 1
        return res

    even_result = np.array([sub(2 * x) for x in range(1, DEG + 1)], dtype=np.int64) % MOD
    odd_result = np.array([sub(2 * x + 1) for x in range(1, DEG + 1)], dtype=np.int64) % MOD

    base_coef = np.zeros((DEG, DEG), dtype=np.int64)
    base_coef[:, -1] = 1
    indices = np.arange(1, DEG + 1, dtype=np.int64)
    invs = np.ones(DEG, dtype=np.int64)
    for i in range(1, DEG + 1):
        idx = indices != i
        base_coef[idx, :-1] += base_coef[idx, 1:] * -i
        base_coef %= MOD
        invs[idx] *= indices[idx] - i
    base_coef *= np_pow(invs % MOD, MOD - 2, MOD)[:, None]
    base_coef %= MOD

    even_coef = even_result[:, None] * base_coef % MOD
    odd_coef = odd_result[:, None] * base_coef % MOD
    even_coef = even_coef.sum(axis=0) % MOD
    odd_coef = odd_coef.sum(axis=0) % MOD

    return even_coef, odd_coef


DEG = 16
MOD = 10 ** 9 + 7
even_coef, odd_coef = lagrange(DEG, MOD)

t = int(input())
buf = []
for _ in range(t):
    n = int(input())
    if n % 2 == 0:
        m = n // 2
        coef = even_coef
    else:
        m = (n - 1) // 2
        coef = odd_coef

    ms = np.ones(DEG, dtype=np.int64)
    for i in range(1, DEG):
        ms[i] = ms[i - 1] * m % MOD

    ans = (ms * coef % MOD).sum() % MOD
    buf.append(ans)

print('\n'.join(map(str, buf)))

Solution (Python):
mod = 10**9 + 7
k = 5


class Lagrange:
    def __init__(self, lst):
        self.lst = lst
        self.mod = mod

    def prd(self, j, x):
        tmp = 1
        for i, (xi, yi) in enumerate(self.lst):
            if j != i:
                tmp *= (x - xi)
                tmp %= self.mod
        return tmp

    def pln(self, x):
        tmp = 0
        for i, (xi, yi) in enumerate(self.lst):
            tmp += yi * (self.prd(i, x) *
                         pow(self.prd(i, xi), self.mod - 2, self.mod))
            tmp %= self.mod
        return tmp


def cmb(x, y):
    if x < y:
        return 0
    tmp = 1
    for i in range(y):
        tmp *= x - i
        tmp *= pow(y - i, mod - 2, mod)
        tmp %= mod
    return tmp


def pln(n):
    tmp = 0
    for x in range(n):
        tmp += cmb(x + k - 1, k - 1) * cmb(n - (2 * x) + k, 2 * k)
        tmp %= mod
    return tmp


lst_eve = [(i, pln(i)) for i in range(0, 2 * (3 * k + 1), 2)]
lst_odd = [(i, pln(i)) for i in range(1, 2 * (3 * k + 1) + 1, 2)]

lag_eve = Lagrange(lst_eve)
lag_odd = Lagrange(lst_odd)

t = int(input())
for _ in range(t):
    n = int(input())
    if n % 2 == 0:
        print(lag_eve.pln(n))
    else:
        print(lag_odd.pln(n))

Solution (Python):
mod = 10**9 + 7
k = 5


class Lagrange:
    def __init__(self, lst):
        self.lst = lst
        self.mod = mod

    def prd(self, j, x):
        tmp = 1
        for i, (xi, yi) in enumerate(self.lst):
            if j != i:
                tmp *= (x - xi)
                tmp %= self.mod
        return tmp

    def pln(self, x):
        tmp = 0
        for i, (xi, yi) in enumerate(self.lst):
            tmp += yi * (self.prd(i, x) *
                         pow(self.prd(i, xi), self.mod - 2, self.mod))
            tmp %= self.mod
        return tmp


def cmb(x, y):
    if x < y:
        return 0
    tmp = 1
    for i in range(y):
        tmp *= x - i
        tmp *= pow(y - i, mod - 2, mod)
        tmp %= mod
    return tmp


def pln(n):
    tmp = 0
    for x in range(n):
        tmp += cmb(x + k - 1, k - 1) * cmb(n - (2 * x) + k, 2 * k)
        tmp %= mod
    return tmp


lst_eve = [(i, pln(i)) for i in range(0, 2 * (3 * k + 1), 2)]
lst_odd = [(i, pln(i)) for i in range(1, 2 * (3 * k + 1) + 1, 2)]

lag_eve = Lagrange(lst_eve)
lag_odd = Lagrange(lst_odd)

t = int(input())
for _ in range(t):
    n = int(input())
    if n % 2 == 0:
        print(lag_eve.pln(n))
    else:
        print(lag_odd.pln(n))

Solution (Python):





import sys
from functools import reduce
import numpy as np

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  
MOD = 10 ** 9 + 7

debug_indent = 0


def debug(*x):
    global debug_indent
    x = list(x)
    indent = 0
    if x[0].startswith("enter") or x[0][0] == ">":
        indent = 1
    if x[0].startswith("leave") or x[0][0] == "<":
        debug_indent -= 1
    x[0] = "  " * debug_indent + x[0]
    print(*x, file=sys.stderr)
    debug_indent += indent


def solve(N):
    Q = reduce(
        np.convolve,
        [[1, -1]] * 16 + [[1, 1]] * 5,
        np.array([1], dtype=np.int64))
    P = np.zeros(6, dtype=np.int64)
    P[5] = 1

    def conv(X, Y):
        n = X.shape[0]
        m = Y.shape[0]
        ret = np.zeros(n + m - 1, dtype=np.int64)
        for i in range(n):
            ret[i:i + m] += X[i] * Y
            ret[i:i + m] %= MOD
        return ret

    while N:
        Qm = Q.copy()
        Qm[1::2] *= -1
        QQm = conv(Q, Qm)

        PQm = conv(P, Qm)
        if N % 2:
            P = PQm[1::2]
        else:
            P = PQm[::2]
        Q = QQm[::2]
        N //= 2
    return P[0]


def main():
    
    T = int(input())
    for i in range(T):
        N = int(input())
        print(solve(N))



T1 = """
4
4
6
10
1000000000
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    0
    11
    4598
    257255556
    """




def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        
        
        from my_module import solve  
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Solution (Python):
def combination(k, r, MOD):
    """kCrを求める"""
    if k < r:
        return 0
    r = min(r, k - r)
    numer, denom = 1, 1
    for l in range(r):
        numer *= (k - l)
        numer %= MOD
        denom *= l + 1
        denom %= MOD
    return numer * pow(denom, MOD - 2, MOD) % MOD


t = int(input())
MOD = 10 ** 9 + 7


for i in range(t):
    n = int(input())
    n -= 5
    res = 0
    for odd_cnt in range(12):
        if n - odd_cnt < 0 or (n - odd_cnt) % 2 == 1:
            continue
        m = (n - odd_cnt) // 2
        res += combination(m + 15, 15, MOD) * combination(11, odd_cnt, MOD)
        res %= MOD
    print(res)

Solution (Python):
MOD = 1000000007

def mult(a, b):
    da = len(a)
    db = len(b)
    res = [0] * (da + db - 1)
    for i in range(da):
        for j in range(db):
            res[i+j] = (res[i+j] + a[i] * b[j]) % MOD
    return res

plus = [1, 1]
minus = [1, -1]

d = [1]
for i in range(5):
    d = mult(d, plus)

for i in range(16):
    d = mult(d,  minus)

a = [0] * 6
a[5] = 1


def flip_odd(d):
    dd = d[:]
    for i in range(1, len(dd), 2):
        dd[i] = -dd[i]
    return dd

def get(a, d, n):
    if n == 0:return a[0]
    dd = flip_odd(d)
    if n % 2 == 1:
        return get(mult(a,dd)[1::2], mult(d, dd)[::2], (n-1) // 2)
    else:
        return get(mult(a,dd)[::2], mult(d,dd)[::2], n // 2)

for _ in range(int(input())):
    n = int(input())
    print(get(a, d, n))

Solution (Python):
MOD = 10 ** 9 + 7
INV0 = pow(81729648000, MOD - 2, MOD)
INV1 = pow(163459296000, MOD - 2, MOD)
t = int(input())
buf = []
for _ in range(t):
    n = int(input())
    m = n // 2

    even = 0
    for i, co in enumerate([-11188800, -11670840, 2429994, 8028877, 4647426, 1368843, 235536, 23988, 1344, 32]):
        even = (even + co * pow(m, i, MOD)) % MOD
    for c in range(m - 2, m + 4):
        even = even * c % MOD
    even = even * INV0 % MOD

    if n % 2 == 0:
        m -= 1

    odd = 0
    for i, co in enumerate(
            [-61387200, -162718920, -80000346, 32588015, 46247060, 20273505, 4868682, 706860, 62040, 3040, 64]):
        odd = (odd + co * pow(m, i, MOD)) % MOD
    for c in range(m - 1, m + 4):
        odd = odd * c % MOD
    odd = odd * INV1 % MOD

    ans = (even + odd) % MOD
    buf.append(ans)

print('\n'.join(map(str, buf)))

Solution (Python):
import numpy as np

MOD = 10 ** 9 + 7

l_matrix = np.zeros((32, 32), np.uint64)
for i in range(16):
    l_matrix[i+16][i] = 1
    l_matrix[i][i+16] = 1
for i in range(15):
    l_matrix[i+1][i] = 1
for i in range(5, 15):
    l_matrix[i+1][i+16] = 1
    
doubling = [l_matrix] 
for _ in range(30):
    doubling.append(doubling[-1] @ doubling[-1] % MOD)

T = int(input())
for _ in range(T):
    N = int(input())
    N += 10
    dp = np.zeros(32, np.uint64)
    dp[0] = 1
    for i, c in enumerate(reversed(format(N, 'b'))):
        if c == '1':
            dp = doubling[i] @ dp
            dp %= MOD
    print(int((dp[15] + dp[31]) % MOD))

Solution (Python):
import sys

def I(): return int(sys.stdin.readline().rstrip())

T = I()
mod = 10**9+7

for i in range(T):
    N = I()
    if N % 2 == 0:
        M = N//2+1
        a = pow(M,15,mod)*pow(1277025750,mod-2,mod)
        a %= mod
        a += pow(M,14,mod)*pow(48648600,mod-2,mod)
        a %= mod
        a += pow(M,13,mod)*29*pow(145945800,mod-2,mod)
        a %= mod
        a += pow(M,12,mod)*pow(1425600,mod-2,mod)
        a %= mod
        a += -pow(M,11,mod)*571*pow(449064000,mod-2,mod)
        a %= mod
        a += -pow(M,10,mod)*pow(62208,mod-2,mod)
        a %= mod
        a += -pow(M,9,mod)*6269*pow(228614400,mod-2,mod)
        a %= mod
        a += pow(M,8,mod)*109*pow(1360800,mod-2,mod)
        a %= mod
        a += pow(M,7,mod)*23227*pow(81648000,mod-2,mod)
        a %= mod
        a += -pow(M,6,mod)*7*pow(518400,mod-2,mod)
        a %= mod
        a += -pow(M,5,mod)*301729*pow(359251200,mod-2,mod)
        a %= mod
        a += -pow(M,4,mod)*4409*pow(8553600,mod-2,mod)
        a %= mod
        a += pow(M,3,mod)*1081139*pow(1513512000,mod-2,mod)
        a %= mod
        a += pow(M,2,mod)*10037*pow(21621600,mod-2,mod)
        a %= mod
        a += -pow(M,1,mod)*47*pow(360360,mod-2,mod)
        a %= mod
        print(a)
    else:
        M = N//2+1
        a = pow(M,15,mod)*pow(1277025750,mod-2,mod)
        a %= mod
        a += pow(M,14,mod)*pow(37837800,mod-2,mod)
        a %= mod
        a += pow(M,13,mod)*53*pow(145945800,mod-2,mod)
        a %= mod
        a += pow(M,12,mod)*pow(399168,mod-2,mod)
        a %= mod
        a += pow(M,11,mod)*319*pow(40824000,mod-2,mod)
        a %= mod
        a += -pow(M,10,mod)*11*pow(3628800,mod-2,mod)
        a %= mod
        a += -pow(M,9,mod)*21893*pow(228614400,mod-2,mod)
        a %= mod
        a += -pow(M,8,mod)*31*pow(141120,mod-2,mod)
        a %= mod
        a += pow(M,7,mod)*9307*pow(81648000,mod-2,mod)
        a %= mod
        a += pow(M,6,mod)*3769*pow(3628800,mod-2,mod)
        a %= mod
        a += pow(M,5,mod)*297287*pow(359251200,mod-2,mod)
        a %= mod
        a += -pow(M,4,mod)*4841*pow(3991680,mod-2,mod)
        a %= mod
        a += -pow(M,3,mod)*87223*pow(56056000,mod-2,mod)
        a %= mod
        a += pow(M,2,mod)*6631*pow(16816800,mod-2,mod)
        a %= mod
        a += pow(M,1,mod)*23*pow(32760,mod-2,mod)
        a %= mod
        print(a)

Solution (Python):
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)*16+j]for j in range(16))%(10**9+7))

Solution (Python):
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)*16+j]for j in range(16))%(10**9+7))

Solution (Python):
import math
M = 1000000007
T = int(input())
for i in range(T):
	n = int(input())
	r = 0
	for i in range((n-5)%2,12,2):
		r+=math.comb(11,i)%M*math.comb((n-i+25)//2,15)%M;
	print(r%M)

Solution (Python):
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)*16+j]for j in range(16))%(10**9+7))

Solution (Python):
for _ in range(int(input())):
	n=int(input())
	print(sum([n**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]][n&1][j]for j in range(16)])%(10**9+7))

Solution (Python):
m=10**9+7
x=[[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]]
for _ in range(int(input())):
	n=int(input())
	print(sum([n**j*x[n&1][j]for j in range(16)])%m)

Solution (Python):
m=1000000007
x=[[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]]
for _ in range(int(input())):
	n=int(input())
	print(sum([pow(n,j,m)*x[n&1][j]%m for j in range(16)])%m)

Solution (Python):
T = int(input())
for _ in range(T):
	n = int(input())
	if n < 5:
		print(0)
	elif n % 2 == 0:
		x = n // 2 - 2
		ans = (37476432000*(x) + 187243792560*(x**2) + 399117903732*(x**3) + 485269948800*(x**4) + 379718819935*(x**5) + 204017288475*(x**6) + 78161197114*(x**7) + 21814113750*(x**8) + 4477585255*(x**9) + 675269595*(x**10) + 73895276*(x**11) + 5705700*(x**12) + 294560*(x**13) + 9120*(x**14) + 128*(x**15))//163459296000
		print(ans % 1000000007)
	else:
		x = n // 2 - 1
		ans = ((-4490640000) * (x) - 9469891440 * (x**2) + 5980311612 * (x**3) + 38927921760 * (x**4) + 55757252005 * (x**5) + 44011832865 * (x**6) + 22464496054 * (x**7) + 7902767730 * (x**8) + 1972993165 * (x**9) + 353017665 * (x**10) + 45000956 * (x**11) + 3991260 * (x**12) + 234080 * (x**13) + 8160 * (x**14) + 128 * (x**15))//163459296000
		print(ans % 1000000007)

Solution (Python):
MOD=10**9+7

def matmul(A,B): 
    res = [[0]*len(B[0]) for _ in [None]*len(A)]
    for i, resi in enumerate(res):
        for k, aik in enumerate(A[i]):
            for j,bkj in enumerate(B[k]):
                resi[j] += aik*bkj
                resi[j] %= MOD
    return res

def matpow(A,p): 
    if p%2:
        return matmul(A, matpow(A,p-1))
    elif p > 0:
        b = matpow(A,p//2)
        return matmul(b,b)
    else:
        return [[1 if i == j else 0 for j in range(len(A))] for i in range(len(A))]

def solve(n):
    pass


import sys
read = sys.stdin.read
readline = sys.stdin.readline



T, = map(int,readline().split())


c = [1, -11, 50, -110, 65, 253, -648, 440, 610 , -1430 ,+ 780 ,+ 780, - 1430 ,  610 , 440, - 648, + 253, + 65, - 110, + 50, - 11, + 1]

m = 21
A = [[0]*m for _ in range(m)]
for i in range(m-1):
    A[i+1][i] = 1
for i in range(m):
    A[i][-1] = -c[i]
    



v = [[0]*(m-1)+[1]]
c = matmul(v,matpow(A,15))



for _ in range(T):
    n, = map(int,readline().split())
    x = matmul(c,matpow(A,n))
    print(x[0][0])

Solution (Python):
mod=10**9+7

const=1
for i in range(1,16):
    const=(const*pow(i,mod-2,mod))%mod

def poly(n):
    if n<=14:
        return 0
    else:
        res=const
        for i in range(15):
            res=(res*(n-i))%mod
        return res

c=[1,5,10,10,5,1]
def conb(n):
    return c[n]


data=[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1]]

for _ in range(int(input())):
    N=int(input())
    ans=0
    for i in range(6):
        temp=0
        for j in range(6-i):
            n=(N+5-i)//2
            temp=(temp+poly(n+10-j)*data[5-i][j])%mod
        temp=(c[i]*temp*2**i)%mod
        ans=(ans+temp)%mod
    print(ans%mod)

Solution (Python):
from functools import lru_cache

@lru_cache(102400)
def t(n, u):
    if u <= 0:
        return 1
    ans = 0
    for k1 in range(0, n + 1):
        for k2 in range(k1 + 1, (n - k1) + 1):
            ans += (k2 - k1) * t(n - k1 - k2, u - 1)
    return ans

def tl(n, u):
    return list(map(lambda x: t(x, u), range(n)))

def d(x):
    return [x[i + 1] - x[i] for i in range(len(x) - 1)]

l = tl(80, 5)
sp = [[], []]

for j in range(2):
    sp[j] = [(i, l[i]) for i in range(j, len(l), 2)]
    
    
    
    

mo = 10 ** 9 + 7

def rev(x):
    global mo
    return pow(x, mo - 2, mo)

def solveKth(s, k):
    global mo
    for u, v in s:
        if u == k:
            return v % mo
    def l(j):
        global mo
        ans = 1
        for i in range(len(s)):
            if i != j:
                ans = ans * (k - s[i][0]) * rev(s[j][0] - s[i][0]) % mo
        return ans
    ans = 0
    for j in range(len(s)):
        ans = (ans + s[j][1] * l(j)) % mo
    return ans

t = int(input())
for _ in range(t):
    x = int(input())
    print(solveKth(sp[x % 2], x))

Solution (Python):
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))