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 sys
sys.setrecursionlimit(10**6)


def ext_euc(a, b):
    if b == 0:
        return 1, 0, a
    y, x, v = ext_euc(b, a % b)
    y -= (a // b) * x
    return x, y, v


def mod_inv(a, mod):
    x, _, _ = ext_euc(a, mod)
    return x % mod


def generate_points(is_odd, mod):
    
    n_points = 16
    points = [None] * n_points
    if is_odd:
        comb_1 = [0] * n_points  
        comb_2 = [0] * n_points  
        comb_1[0] = 1
        comb_2[0] = 1
        for n in range(1, n_points):
            comb_1[n] = comb_1[n - 1] * (n + 4) * mod_inv(n, mod) % mod
            v = comb_2[n - 1] * (2 * n + 10) * (2 * n + 9) % mod
            v *= mod_inv(2 * n, mod) * mod_inv(2 * n - 1, mod) % mod
            comb_2[n] = v % mod
        for n in range(n_points):
            N = 2 * n + 5
            val = 0
            for k in range(n + 1):
                val += comb_1[k] * comb_2[n - k]
                val %= mod
            points[n] = (N, val)
    else:
        comb_1 = [0] * n_points  
        comb_2 = [0] * n_points  
        comb_1[0] = 1
        comb_2[0] = 11  
        for n in range(1, n_points):
            comb_1[n] = comb_1[n - 1] * (n + 4) * mod_inv(n, mod) % mod
            v = comb_2[n - 1] * (2 * n + 11) * (2 * n + 10) % mod
            v *= mod_inv(2 * n + 1, mod) * mod_inv(2 * n, mod) % mod
            comb_2[n] = v % mod
        for n in range(n_points):
            N = 2 * n + 6
            val = 0
            for k in range(n + 1):
                val += comb_1[k] * comb_2[n - k]
                val %= mod
            points[n] = (N, val)
    return points


def lagrange_interpolation(points, k, mod):
    n_points = len(points)
    
    
    ret = 0
    for n in range(n_points):
        x, y = points[n]
        y_coef = 1
        for i in range(n_points):
            if i == n:
                continue
            xi, _ = points[i]
            y_coef *= k - xi
            y_coef *= mod_inv(x - xi, mod)
        ret += y * y_coef
        ret %= mod
    return ret


def main():
    MOD = 10**9 + 7
    T = int(input())
    test_cases = [int(input()) for _ in range(T)]
    odd_points = generate_points(True, MOD)
    even_points = generate_points(False, MOD)
    for N in test_cases:
        if N < 5:
            print(0)
        elif N % 2 == 0:
            print(lagrange_interpolation(even_points, N, MOD))
        else:
            print(lagrange_interpolation(odd_points, N, MOD))


if __name__ == '__main__':
    main()

Solution (Python):


import math
MOD = 10**9+7

def resolve():
    T = int(input())
    for _ in range(T):
        N = int(input())
        r = 0
        for i in range((N-5)%2, 12, 2):
            r += math.comb(11,i) % MOD * math.comb((N-i+25)//2, 15) % MOD
        print(r%MOD)
    return
resolve()

Solution (Python):
mod = 10**9+7
def mul(f,g):
    n = len(f)
    m = len(g)
    h = [0]*(n+m-1)
    for i in range(n):
        for j in range(m):
            h[i+j] += f[i]*g[j]
            h[i+j] %= mod
    return h

def rev(f):
    h = [0]*len(f)
    for i in range(len(f)):
        h[i] += f[i]
        if i%2==1:
            h[i] *= -1
        h[i] %= mod
    return h

def add(f,g):
    if len(f)<len(g):
        f,g = g,f
    g += [0]*(len(f)-len(g))
    h = [0]*len(f)
    for i in range(len(f)):
        h[i] = f[i]+g[i]
        h[i] %= mod
    return h

def coef(n,P,Q):
    if n==0:
        return P[0]%mod
    q = mul(Q,rev(Q))[::2]
    if n%2==0:
        p = mul(P,rev(Q))[::2]
    else:
        p = mul(P,rev(Q))[1::2]
    return coef(n//2,p,q)

P = [0,0,0,0,0,1]
Q = [1]
for i in range(5):
    Q = mul(Q,[1,1])
for i in range(16):
    Q = mul(Q,[1,-1])

T = int(input())
for i in range(T):
    N = int(input())
    print(coef(N,P,Q))

Solution (Python):


import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

mod = 10 **9 + 7


def calc(n):
    ans = 0
    if n & 1:
        Y = [33746491, 897911890, 741553367, 922649390, 82466138, 30593036, 407570181, 119032926, 718747607, 27251510, 15690675, 2549638, 225225, 11620, 330, 4]
    else:
        Y = [0,       296640693, 751721723, 240221668, 869628520, 30593036, 407570181, 119032926, 718747607, 27251510, 15690675, 2549638, 225225, 11620, 330, 4]

    x = 1
    for y in Y:
        ans = (ans + x*y%mod) % mod
        x = x*n%mod
    ans = ans * pow(167382319104000, mod-2, mod) % mod
    return ans

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)

    ans = [0] * N
    for i in range(N):
        n = next(it)
        ans[i] = calc(n)

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Solution (Python):


import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from functools import lru_cache

mod = 10 **9 + 7


@lru_cache(100)
def calc(n):
    ans = 0
    if n & 1:
        Y = [37033746750,-19102088250,-75258447165,+8922649446,+41082466425,+12030593120,-2592429840,-1880967088,-281252400,+27251510,+15690675,+2549638,+225225,+11620,+330,+4]
    else:
        Y = [0,         -98703360000,-108248279040,+4240221696,+40869628800,+12030593120,-2592429840,-1880967088,-281252400,+27251510,+15690675,+2549638,+225225,+11620,+330,+4]

    x = 1
    for i, y in enumerate(Y):
        ans = (ans + x*(y%mod) % mod) % mod
        x = x*n%mod
    ans = ans * pow(167382319104000, mod-2, mod) % mod
    return ans

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)

    ans = [0] * N
    for i in range(N):
        n = next(it)
        ans[i] = calc(n)

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Solution (Python):


import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from functools import lru_cache

mod = 10 **9 + 7


@lru_cache(100)
def calc(n):
    m = (n-5) // 2

    
    return (
        (1+m)*(2+m)*(3+m)%mod*(4+m)*(5+m)%mod*(
            1025024*pow(m,10,mod)+3003*(-4+n)%mod*(-3+n)*(-2+n)%mod*(-1+n)*n*(1+n)%mod*(2+n)*(3+n)%mod*(4+n)*(5+n)%mod
            -549120*pow(m,9,mod)*(-1+10*n)%mod
            +42240*pow(m,8,mod)*(-398+45*n*(-1+7*n))%mod
            -369600*pow(m,7,mod)*(3+2*(-2+n)*n*(49+26*n)%mod)%mod
            +2688*pow(m,6,mod)*(33529+75*n*(-33-679*n+91*n**3)%mod)%mod
            -336*pow(m,5,mod)*(88065+2*n*(426107+7*n*(-6675+13*n*(-2420+9*n*(5+22*n)%mod))%mod))%mod
            +560*pow(m,4,mod)*(-291598+n*(216249+7*n*(95465+26*n*(-495+n*(-980+11*n*(3+5*n))%mod))%mod))%mod
            -30*pow(m,3,mod)*(-3080960+n*(-10447602+7*n*(854525+13*n*(93170+n*(-15295+22*n*(-714+5*n*(7+6*n)%mod))%mod))%mod))%mod
            +2*pow(m,2,mod)*(28412712+25*n*(-3433650+n*(-4123841+13*n*(189882+n*(142177+22*n*(-1344+n*(-791+27*n*(2+n))%mod))%mod))%mod))%mod
            -m*(30149280+n*(31294296+n*(-93275400+13*n*(-3808420+n*(2988195+11*n*(111678+25*n*(-1302+n*(-456+n*(45+14*n)%mod))%mod))%mod))%mod))%mod
        )%mod*pow(1307674368000%mod, mod-2, mod)%mod
    )

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)

    ans = [0] * N
    for i in range(N):
        n = next(it)
        ans[i] = calc(n)

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Solution (Python):


import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from functools import lru_cache

mod = 10 **9 + 7


@lru_cache(100)
def calc(n):
    m = (n-5) // 2

    
    return (
        (1+m)*(2+m)*(3+m)*(4+m)*(5+m)%mod*(
            1025024*pow(m,10,mod)+3003*(-4+n)%mod*(-3+n)%mod*(-2+n)%mod*(-1+n)*n*(1+n)%mod*(2+n)%mod*(3+n)%mod*(4+n)%mod*(5+n)%mod
            -549120*pow(m,9,mod)*(-1+10*n)%mod
            +42240*pow(m,8,mod)*(-398+45*n*(-1+7*n)%mod)%mod
            -369600*pow(m,7,mod)*(3+2*(-2+n)*n*(49+26*n)%mod)%mod
            +2688*pow(m,6,mod)*(33529+75*n*(-33-679*n+91*n**3)%mod)%mod
            -336*pow(m,5,mod)*(88065+2*n*(426107+7*n*(-6675+13*n*(-2420+9*n*(5+22*n)%mod)%mod)%mod)%mod)%mod
            +560*pow(m,4,mod)*(-291598+n*(216249+7*n*(95465+26*n*(-495+n*(-980+11*n*(3+5*n)%mod)%mod)%mod)%mod)%mod)%mod
            -30*pow(m,3,mod)*(-3080960+n*(-10447602+7*n*(854525+13*n*(93170+n*(-15295+22*n*(-714+5*n*(7+6*n)%mod)%mod)%mod)%mod)%mod)%mod)%mod
            +2*pow(m,2,mod)*(28412712+25*n*(-3433650+n*(-4123841+13*n*(189882+n*(142177+22*n*(-1344+n*(-791+27*n*(2+n)%mod)%mod)%mod)%mod)%mod)%mod)%mod)%mod
            -m*(30149280+n*(31294296+n*(-93275400+13*n*(-3808420+n*(2988195+11*n*(111678+25*n*(-1302+n*(-456+n*(45+14*n)%mod)%mod)%mod)%mod)%mod)%mod)%mod)%mod)%mod
        )%mod*pow(1307674368000%mod, mod-2, mod)%mod
    )

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)

    ans = [0] * N
    for i in range(N):
        n = next(it)
        ans[i] = calc(n)

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Solution (Python):


import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from collections import Counter

mod = 10 **9 + 7


def calc(n):
    m = (n-5) // 2

    
    return (
        (1+m)*(2+m)*(3+m)*(4+m)*(5+m)%mod*(
            1025024*pow(m,10,mod)+3003*(-4+n)*(-3+n)*(-2+n)*(-1+n)*n*(1+n)*(2+n)*(3+n)*(4+n)*(5+n)%mod
            -549120*pow(m,9,mod)*(-1+10*n)%mod
            +42240*pow(m,8,mod)*(-398+45*n*(-1+7*n))%mod
            -369600*pow(m,7,mod)*(3+2*(-2+n)*n*(49+26*n))%mod
            +2688*pow(m,6,mod)*(33529+75*n*(-33-679*n+91*n**3))%mod
            -336*pow(m,5,mod)*(88065+2*n*(426107+7*n*(-6675+13*n*(-2420+9*n*(5+22*n)))))%mod
            +560*pow(m,4,mod)*(-291598+n*(216249+7*n*(95465+26*n*(-495+n*(-980+11*n*(3+5*n))))))%mod
            -30*pow(m,3,mod)*(-3080960+n*(-10447602+7*n*(854525+13*n*(93170+n*(-15295+22*n*(-714+5*n*(7+6*n)))))))%mod
            +2*pow(m,2,mod)*(28412712+25*n*(-3433650+n*(-4123841+13*n*(189882+n*(142177+22*n*(-1344+n*(-791+27*n*(2+n))))))))%mod
            -m*(30149280+n*(31294296+n*(-93275400+13*n*(-3808420+n*(2988195+11*n*(111678+25*n*(-1302+n*(-456+n*(45+14*n)))))))))%mod
        
        )%mod*pow(1307674368000%mod, mod-2, mod)%mod
    )

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)

    ans = [0] * N
    for i in range(N):
        n = next(it)
        ans[i] = calc(n)

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





import numpy as np

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]

  
  
Q = np.array([1,0,-1], np.int64)
for _ in range(4):
    Q = np.convolve(Q, Q)
    
P = np.zeros_like(Q)[:-11]
P[0] = P[1] = 1
for _ in range(10):
    P = np.convolve(P, np.array([1,1]))
  
def f(N):
  return coef_of_generating_function(P, Q, N)

def solve(n):
  if n < 5:
    print(0)
    return
  else:
    print(f(n-5))
    return

q = I()    
for _ in range(q):
  solve(I())

Solution (Python):
import sys
input = sys.stdin.readline

mod=10**9+7

def Combi2(a,b):
    if b>a:
        return 0
    ANS=1
    for i in range(min(b,a-b)):
        ANS=ANS*(a-i)*pow(min(b,a-b)-i,mod-2,mod)%mod

    return ANS%mod

T=int(input())
for tests in range(T):
    N=int(input())

    ANS=0

    for i in range(12):
        if (N-i-5)%2==0:
            ANS=ANS+Combi2(11,i)*Combi2((N-i-5)//2+15,15)
            ANS%=mod
            
    print(ANS)

Solution (Python):
def c(n,r):
    a = 1
    for i in range(r):
        a *= (n-i)
        a %= mod
    return a*ifact[r]%mod

mod = pow(10,9)+7
inv = [0,1]
fact = [1,1]
ifact = [1,1]
for i in range(2,16):
    inv.append(inv[mod%i]*(mod-mod//i)%mod)
    fact.append(i*fact[-1]%mod)
    ifact.append(ifact[-1]*inv[i]%mod)

t = int(input())
for _ in range(t):
    ans = 0
    n = int(input())-5
    for o in range(12):
        m = n-o
        if (m<0 or m&1):
            continue
        ans += c(11,o)*c(m//2+15,15)
        ans %= mod
    print(ans)

Solution (Python):
def c(n,r):
    a = 1
    for i in range(r):
        a *= (n-i)
        a %= mod
    return a*ifact[r]%mod

mod = pow(10,9)+7
inv = [0,1]
fact = [1,1]
ifact = [1,1]
for i in range(2,16):
    inv.append(inv[mod%i]*(mod-mod//i)%mod)
    fact.append(i*fact[-1]%mod)
    ifact.append(ifact[-1]*inv[i]%mod)

t = int(input())
for _ in range(t):
    ans = 0
    n = int(input())-5
    for o in range(12):
        m = n-o
        if (m<0 or m&1):
            continue
        ans += c(11,o)*c(m//2+15,15)
        ans %= mod
    print(ans)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





def solve(n):
  if n < 5:
    print(0)
    return
  n -= 5
  ans = 0
  for i in range(12):
    if (n-i)%2==0 and n>=i:
      k = (n-i)//2
      x = gyaku_kaijo(15)
      for j in range(15):
        x *= k+j+1
        x %= MOD
      ans += nCr(11,i)*x
      ans %= MOD
  print(ans)
  return

def main():
  N = I()
  for _ in range(N):
    solve(I())

main()

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


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

    def prd(self, j, x):
        tmp = 1
        for i, (xi, yi) in enumerate(self.lst):
            if j != i:
                tmp *= (x - xi)
                tmp %= 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), mod - 2, mod))
            tmp %= 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, 6 * k + 1, 2)]
lst_odd = [(i, pln(i)) for i in range(1, 6 * k + 2, 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
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





import numpy as np
arr = np.matrix([
  [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
  [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
  [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
  [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
])



arrs = [arr]
for _ in range(30):
  arrs.append((arrs[-1]**2)%MOD)

def solve(n):
  if n < 5:
    print(0)
    return
  n -= 5
  v = np.matrix([
  [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
  ])
  for k in range(31)[::-1]:
    if (n>>k)&1:
      v = np.dot(v,arrs[k])%MOD
  print(v.tolist()[0][-1])

def main():
  N = I()
  for _ in range(N):
    solve(I())

main()

Solution (Python):
def solve(N):
  if N<=4:
    print(0)
    return 0
  X=[]
  if N&1:
    X=[13305600,45718704,-15523260,-8918200,281505,538692,93135,7200,270,4]
  else:
    X=[-25704000,1155744,11833500,-1132660,-1022385,-27048,27825,3960,210,4]
  N=(N>>1)<<1
  Y=[1]
  for i in range(10):
    Y.append(Y[i]*N)
  P=1
  for i in range(6):
    P*=N+i+i
  Q=0
  for i in range(10):
    Q+=Y[i]*X[i]
  Q*=P
  Q//=167382319104000
  print(Q%(10**9+7))

for i in range(int(input())):
  solve(int(input()))

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

MAX = 40
mod = 10**9+7
fact = [1]*(MAX+1)
for i in range(1, MAX+1):
    fact[i] = (fact[i-1]*i) % mod

inv = [1]*(MAX+1)
for i in range(2, MAX+1):
    inv[i] = inv[mod % i]*(mod-mod//i) % mod

fact_inv = [1]*(MAX+1)
for i in range(1, MAX+1):
    fact_inv[i] = fact_inv[i-1] * inv[i] % mod

def comb(n, k):
    if n < k:
        return 0
    return fact[n] * fact_inv[n-k] * fact_inv[k] % mod

def f(n):
  tmp = 0
  for x in range(n):
    tmp += comb(x+4,4)*comb(n-2*x+5,10)
    tmp %= mod
  return tmp

c0 = [(i*2, f(i*2)) for i in range(16)]
c1 = [(i*2+1, f(i*2+1)) for i in range(16)]

a0 = Lagrange(c0)
a1 = Lagrange(c1)

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

Solution (Python):
import numpy as np

DEG = 16
MOD = 10 ** 9 + 7

even_coef = np.array(
    [0, 530289159, 384702529, 781298570, 90480784, 891754269, 348592099, 833888760, 898908474,
     505425073, 312827475, 794140068, 663894405, 565007911, 300594255, 98196225], dtype=np.int64)
odd_coef = np.array(
    [0, 231379733, 814507152, 631092340, 912089085, 58225824, 706460451, 264043077, 508834119,
     558179703, 136167972, 662064550, 384875310, 496818569, 537065939, 98196225], dtype=np.int64)

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)))