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:
from functools import lru_cache

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

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

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

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

for j in range(2):
    sp[j] = [(i, l[i]) for i in range(j, len(l), 2)]
    # u = [l[i] for i in range(j, len(l), 2)]
    # for k in range(30):
    #     print(u)
    #     u = d(u)

mo = 10 ** 9 + 7

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

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

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

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7

def fft_convolve(f, g):
    """
    数列 (多項式) f, g の畳み込みの計算．上下 15 bitずつ分けて計算することで，
    30 bit以下の整数，長さ 250000 程度の数列での計算が正確に行える．
    """
    Lf, Lg = f.shape[-1], g.shape[-1]
    Lg = g.shape[-1]
    L = Lf + Lg - 1
    fft_len = 1 << L.bit_length()
    fh, fl = f >> 15, f & (1 << 15) - 1
    gh, gl = g >> 15, g & (1 << 15) - 1

    def conv(f, g):
        Ff = np.fft.rfft(f, fft_len)
        Fg = np.fft.rfft(g, fft_len)
        h = np.fft.irfft(Ff * Fg)
        return np.rint(h)[..., :L].astype(np.int64) % MOD

    x = conv(fl, gl)
    z = conv(fh, gh)
    y = conv(fl + fh, gl + gh) - x - z
    return (x + (y << 15) + (z << 30)) % MOD

def coef_of_generating_function(P, Q, N):
    """compute the coefficient [x^N] P/Q of rational power series.

    Parameters
    ----------
    P : np.ndarray
        numerator.
    Q : np.ndarray
        denominator
        Q[0] == 1 and len(Q) == len(P) + 1 is assumed.
    N : int
        The coefficient to compute.
    """
    assert Q[0] == 1 and len(Q) == len(P) + 1

    def convolve(f, g):
        return fft_convolve(f, g)

    while N:
        Q1 = np.empty_like(Q)
        Q1[::2] = Q[::2]
        Q1[1::2] = MOD - Q[1::2]
        P = convolve(P, Q1)[N & 1::2]
        Q = convolve(Q, Q1)[::2]
        N >>= 1
    return P[0]

den = np.array([1,-1], np.int64)
for _ in range(5):
    den = np.convolve(den, np.array([1,-2,0,2,-1]))

num = np.zeros_like(den)[:-1]
num[5] = 1

def f(N):
    return coef_of_generating_function(num, den, N)

T = int(readline())
nums = map(int, read().split())
for n in nums:
    print(f(n))

Submission status: Runtime Error

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 = [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]
    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 i, y in enumerate(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)

    if N == 4: raise 1

    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: Runtime Error

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 = [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]
    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, 25496 38, 225225, 11620, 330, 4]

    x = 1
    for i, y in enumerate(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)

    if N == 4: raise 1

    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: Runtime Error

Solution code:
#!python3

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

mod = 10 **9 + 7

memo = dict()

def calc(n):
    if n in memo: return memo[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
    memo[n] = ans
    return ans

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

    if N == 4: raise 1

    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: Runtime Error

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

    if N == 4: raise 1

    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: Runtime Error

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
        #print(i, y, x)
        x = x*n%mod
        #ans = ans + x * y
    ans = ans * pow(167382319104000, mod-2, mod) % mod
    #ans /= 167382319104000
    return ans

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

    if N == 4: raise 1

    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: Runtime Error

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
        #) // 1307674368000
        )%mod*pow(1307674368000%mod, mod-2, mod)%mod
    )

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

    if N == 4: raise 1

    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: Runtime Error

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

    if N == 4: raise 1

    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: Runtime Error

Solution code:
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <bitset>
#include <complex>
#include <unistd.h>
#include <cassert>
#include <cctype>
#include <random>
#include <time.h>
#include <functional>
#define _USE_MATH_DEFINES
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef pair<double, ll> pdlg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef tuple<ll, ll, ll, ll> tlglglglg;
typedef tuple<double, double, double> tddd;
typedef complex<double> xy_t;
typedef vector<ll> vll;
typedef vector< vector<ll> > matrix;
typedef unsigned int uint;
typedef unsigned long long ull;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
template <class T> using VVV = V<VV<T>>;
#define REP(i, x, y) for(ll i = (ll)x; i < (ll)y; i++)
#define DREP(i, x, y, d) for(ll i = (ll)x; i < (ll)y; i += (ll)d)
#define PER(i, x, y) for(ll i = (ll)x; i > (ll)y; i--)
#define DPER(i, x, y, d) for(ll i = (ll)x; i > (ll)y; i -= (ll)d)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
double pi = 3.141592653589793;
ll mod = 1000000007;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;
int iinf = intmax / 8;
ll inf = llmax / 8;
double eps = 1e-12;
void yesno(bool ok, string yes = "Yes", string no = "No") {
    if (ok) {
        cout << yes << endl;
    } else {
        cout << no << endl;
    }
}

template <uint MD> struct ModInt {
    using M = ModInt;
    const static M G;
    uint v;
    ModInt(ll _v = 0) { set_v(uint(_v % MD + MD)); }
    M& set_v(uint _v) {
        v = (_v < MD) ? _v : _v - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(uint(ull(v) * r.v % MD)); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    bool operator==(const M& r) const { return v == r.v; }
    M pow(ll n) const {
        M x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    M inv() const { return pow(MD - 2); }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
using Mint = ModInt<1000000007>;

vector<Mint> frac;
vector<Mint> invfrac;

void fracinvfrac(ll n) {
    frac = vector<Mint>(n + 1);
    invfrac = vector<Mint>(n + 1);
    frac[0] = 1;
    for (int i = 1; i <= n; i++) {
        frac[i] = frac[i - 1] * i;
    }
    invfrac[n] = (Mint)1 / frac[n];
    for (int i = n - 1; i >= 0; i--) {
        invfrac[i] = invfrac[i + 1] * (i + 1);
    }
}

Mint modcombi(ll x, ll y) {
    if (x < y || y < 0) {
        return 0;
    } else if (y == 0) {
        return 1;
    } else {
        return frac[x] * invfrac[x - y] * invfrac[y];
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll loop;
    cin >> loop;
    fracinvfrac(100010);
    REP(i, 0, loop) {
        ll N;
        cin >> N;
        N += 5;
        Mint ans = 0;
        ll num = 0;
        while (N >= 10) {
            ans += modcombi(N, 10) * modcombi(num + 5, 5);
            N -= 2;
            num++;
        }
        cout << ans << endl;
    }
}