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



Sample input:
4
4
6
10
1000000000


Sample output:
0
11
4598
257255556

Submission status: Wrong Answer

Solution code:
import numpy as np
conv=np.convolve
def beki(P,Q,n):
    while n:
        Q1=Q.copy()
        Q1[1::2]=-Q[1::2]

        P=conv(P,Q1)[n&1::2]
        Q=conv(Q,Q1)[::2]
        n>>=1
    return P[0]

mod=10**9+7
t=int(input())
p=[0,0,0,0,0,1]
q=[1]
for _ in range(16):
    q=conv(q,[-1,1])
for _ in range(5):
    q=conv(q,[1,1])
for i in range(t):
    n=int(input())
    print(beki(p,q,n)%mod)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()


def main():
    """
    形式的冪級数を用いる問題。maspyさん解説と以下の解説を参照。
    将来解き直す時のメモとしてのせておく。
    https://atcoder.jp/contests/aising2020/tasks/aising2020_f
    """
    T = int(input())
    for _ in range(T):
        N = int(input())
        print(0)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
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] #doubling[i] = (l_matrix) ** (2 ** i) % MOD
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((dp[15] + dp[31]) % MOD)
    #print(dp)

Submission status: Wrong Answer

Solution code:
import numpy as np

MOD = 10 ** 9 + 7

l_matrix = np.zeros((32, 32), np.int64)
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] #doubling[i] = (l_matrix) ** (2 ** i) % MOD
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.int64)
    dp[0] = 1
    for i, c in enumerate(reversed(format(N, 'b'))):
        if c == '1':
            dp = doubling[i] @ dp
            dp %= MOD
    print((dp[15] + dp[31]) % MOD)
    #print(dp)

Submission status: Wrong Answer

Solution code:
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))

Submission status: Wrong Answer

Solution code:
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))

Submission status: Wrong Answer

Solution code:
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 - 2
		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)

Submission status: Wrong Answer

Solution code:
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)

Submission status: Wrong Answer

Solution code:
T=int(input())
mod=10**9+7
def inv(x):
    return pow(x,mod-2,mod)
for case in range(T):
    N=int(input())
    if N%2==0:
        K=N//2
        #2K
        for i in range(1,12):
            exec("K{0}=pow(K,{0},mod)".format(str(i)))
        tmp1=(K *(32 *K11 + 480 *K10 + 2464 *K9 + 3300 *K8 - 12309 *K7 - 40590 *K6 - 6248 *K5 + 93390 *K4 + 69377 *K3 - 58740 *K2 - 53316 *K + 2160))
        tmp2=(K* (32 *K11 + 288 *K10 + 352 *K9 - 3300 *K8 - 8349 *K7 + 10494 *K6 + 40876 *K5 - 4950 *K4 - 69883 *K3 - 13332 *K2 + 36972 *K + 10800))
        tmp1%=mod
        tmp2%=mod
        tmp=(tmp1+tmp2)%mod
        tmp=tmp*inv(14968800)
        tmp%=mod
        print(tmp)
        
    else:
        K=(N-1)//2
        #2K+1

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline

mod = 10**9+7

T = int(input())
tw = []
th = []
for i in range(T):
    n = int(input())
    if n<5:
        print(0)
    n -= 4
    
    tmp = (1-n)**7
    tmp = tmp*((1-n**4)**5)
    print(pow(tmp,mod-2,mod))

Submission status: Wrong Answer

Solution code:
T = int(input())
MOD = 10 ** 9 + 7
for _ in range(T):
    N = int(input())
    ans = 1
    ans *= N+5
    ans *= N+4
    ans *= N+3
    ans *= N+2
    ans *= N+1
    ans *= N
    ans *= N-1
    ans *= N-2
    ans *= N-3
    ans *= N-4
    ans //= 3628800
    ans %= MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
T = int(input())
MOD = 10 ** 9 + 7
for _ in range(T):
    N = int(input())
    ans = 1
    ans *= N+5
    ans *= N+4
    ans *= N+3
    ans *= N+2
    ans *= N+1
    ans *= N
    ans *= N-1
    ans *= N-2
    ans *= N-3
    ans *= N-4
    ans /= 3628800
    ans %= MOD
    print(ans)

Submission status: Wrong Answer

Solution code:
for i in range(int(input())):
  N=int(input())
  if N<=4:
    print(0)
    continue
  Y=[1]
  mod=10**9+7
  for i in range(15):
    Y.append(Y[-1]*N)
  P=1
  for i in range(-4,15,2):
    P*=N+i
  P*=(4*Y[5]+130*Y[4]+1280*Y[3]+2825*Y[2]-10524*N-19125)
  P//=167382319104000
  if N&1:
    P+=1
  print(P%mod)

Submission status: Wrong Answer

Solution code:
for i in range(int(input())):
  N=int(input())
  Y=[1]
  mod=10**9+7
  for i in range(15):
    Y.append(Y[-1]*N)
  P=1
  for i in range(-4,15,2):
    P*=N+i
  P*=(4*Y[5]+130*Y[4]+1280*Y[3]+2825*Y[2]-10524*N-19125)
  P//=167382319104000
  if N&1:
    P+=1
  print(P%mod)

Submission status: Wrong Answer

Solution code:
for i in range(int(input())):
  N=int(input())
  Y=[1]
  mod=10**9+7
  for i in range(15):
    Y.append(Y[-1]*N)
  P=1
  for i in range(-4,15,2):
    P*=N+i
  P*=(4*Y[5]+130*Y[4]+1280*Y[3]+2825*Y[2]-10524*N-19125)
  P//=167382319104000
  print(P%mod)

Submission status: Wrong Answer

Solution code:
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(60, 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):
    for u, v in s:
        if u == k:
            return v
    global 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))

Submission status: Time Limit Exceeded

Solution code:
N = int(input().strip())

for i in range(N):
    c = int(input().strip())
    x=0
    y=0
    z=0
    w=0
    q=0
    for j in range(c):
        for s in range(j):
            for s1 in range(int(j//2+1)):
                x+=s1**2+(s-s1)**2
                x//=10**9+7
                for n in range(j-s):
                    for n1 in range(int(n//2+1)):
                        x+=n1**2+(n-n1)**2
                        x//=10**9+7
                        for u in range(j-s-n):
                            for u1 in range(int(u//2+1)):
                                z+=u1**2+(u-u1)**2
                                z//=10**9+7
                                for k in range(j-s-n-u):
                                    for k1 in range(int(k//2+1)):
                                        w+=k1**2+(k-k1)**2
                                        w//=10**9+7
                                        for e in range(j-s-n-u):
                                            for e1 in range(int(e//2+1)):
                                                q+=e1**2+(e-e1)**2
                                                q//=10**9+7
    print((x+y+z+w+q)//(10**9+7))

Submission status: Accepted

Solution code:
# Ref: https://betrue12.hateblo.jp/entry/2020/07/12/060026
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):
    # Lagrange補完するためのデータ点を計算
    n_points = 16
    points = [None] * n_points
    if is_odd:
        comb_1 = [0] * n_points  # (n+4)_C_4
        comb_2 = [0] * n_points  # (2n+10)_C_10
        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  # (k+4)_C_4
        comb_2 = [0] * n_points  # (2n+11)_C_10
        comb_1[0] = 1
        comb_2[0] = 11  # 11_C_10
        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)
    # points を通る n_points - 1 次の多項式 の k での値を求める
    # ref: https://mathtrain.jp/hokan
    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()

Submission status: Accepted

Solution code:
#写経
#https://atcoder.jp/contests/aising2020/submissions/15190580
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()

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
#!python3

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

Submission status: Accepted

Solution code:
#!python3

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

Submission status: Accepted

Solution code:
#!python3

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

Submission status: Accepted

Solution code:
#!python3

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

Submission status: Accepted

Solution code:
#!python3

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

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

#############
# Functions #
#############

######INPUT######
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)]

######OUTPUT######
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()

#####Shorten#####
def DD(arg): return defaultdict(arg)

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

######Combination######
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

######Factorization######
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

#####MakeDivisors######
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

#####MakePrimes######
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

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

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

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

#####ChangeBase#####
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]

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

#############
# Main Code #
#############

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

mod=10**9+7

def Combi2(a,b):# 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)

Submission status: Accepted

Solution code:
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)