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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

#from collections import defaultdict
#from heapq import heappush, heappop
#import numpy as np
import sys
from functools import reduce
import numpy as np

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
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():
    # parse input
    T = int(input())
    for i in range(T):
        N = int(input())
        print(solve(N))


# tests
T1 = """
4
4
6
10
1000000000
"""


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

# add tests above


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":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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(int((dp[15] + dp[31]) % MOD))
    #print(dp)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD=10**9+7

def matmul(A,B): # 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): #A^p mod M
    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
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

#n,k,*a = map(int,read().split())

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]
    
#print(A)


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

#print(c)

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

Submission status: Accepted

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