Problem:


Score : 800 points

Problem Statement

There are N squares lining up in a row, numbered 1 through N from left to right.
Initially, all squares are white.
We also have N-1 painting machines, numbered 1 through N-1.
When operated, Machine i paints Square i and i+1 black.

Snuke will operate these machines one by one.
The order in which he operates them is represented by a permutation of (1, 2, ..., N-1), P, which means that the i-th operated machine is Machine P_i.

Here, the score of a permutation P is defined as the number of machines that are operated before all the squares are painted black for the first time, when the machines are operated in the order specified by P.
Snuke has not decided what permutation P to use, but he is interested in the scores of possible permutations.
Find the sum of the scores over all possible permutations for him.
Since this can be extremely large, compute the sum modulo 10^9+7.

Constraints

2 \leq N \leq 10^6

Input

Input is given from Standard Input in the following format:

N

Output

Print the sum of the scores over all possible permutations, modulo 10^9+7.

Sample Input 1

4

Sample Output 1

16

There are six possible permutations as P.
Among them, P = (1, 3, 2) and P = (3, 1, 2) have a score of 2, and the others have a score of 3.
Thus, the answer is 2 \times 2 + 3 \times 4 = 16.

Sample Input 2

2

Sample Output 2

1

There is only one possible permutation: P = (1), which has a score of 1.

Sample Input 3

5

Sample Output 3

84

Sample Input 4

100000

Sample Output 4

341429644



Sample input:
4


Sample output:
16

Submission status: Time Limit Exceeded

Solution code:
import itertools
P=10**9+7
N=int(input())
S=list(itertools.permutations(range(N-1),N-1))
scoresum=0
for sg in S:
    score=0
    L=[0 for i in range(N)]
    W=N
    for i in range(N-1):
        if L[sg[i]]==0:
            W-=1
        L[sg[i]]=1
        if L[sg[i]+1]==0:
            W-=1
        L[sg[i]+1]=1
        if W==0:
            score=i+1
            break
    scoresum+=score
print(scoresum)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
import collections
n = int(input())
machine = []
[machine.append(i) for i in range(n-1)]
result = []
for i in permutations(machine):
    l = []
    [l.append(i) for i in range(n)]
    score = 0
    for j in i:
        l[j] = -1
        l[j + 1] = -1
        score += 1
        if(all(x == -1 for x in l)):
            result.append(score)
            break
temp = collections.Counter(result)
ans = 0
for k,v in temp.items():
    ans += k*v
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import itertools

n = int(input())
seq = [x for x in range(1,n)]
test_list = list(itertools.permutations(seq))
score = 0

for i in test_list:
    key = True
    ans_list = []
    sc = 0
    for j in i:
        if key:
            ans_list.append(j)
            ans_list.append(j+1)

            ans_num = len(set(ans_list))
            sc += 1
            if ans_num == n:
                key = False

    score += sc

print(score % (10**9 + 7))

Submission status: Accepted

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


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


fac = [1]*(N+1)
for i in range(1,N+1):
    fac[i] = (fac[i-1]*i) % mod

fac_inverse = [1]*(N+1)
for i in range(1,N+1):
    fac_inverse[i] = pow(fac[i],mod-2,mod)


def nCr(n,r):
    if n < r:
        return 0
    return (fac[n]*fac_inverse[r]*fac_inverse[n-r]) % mod


A = [0]*(N+1)  # Ai = i回以下マシンを稼働することで、全て黒く塗られるような順列の個数
for i in range(N+1):
    A[i] = (fac[i]*fac[N-1-i]*nCr(i-1,N-1-i)) % mod

ans = 0
for i in range(1,N):
    ans += i*(A[i]-A[i-1])
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:

"""

https://atcoder.jp/contests/agc023/tasks/agc023_c

完全に無駄になる(すべて塗られている後に動く)マシンの数を数えればいい
つまり、取り除いていくことを考える
→取り除くと、その両側は取り除けない

マシンの総数は (N-1)! * (N-1)
1,N-1のマシンは取り除かれることはない

N-1 の順列のうち、隣り合う数字が選ばれる or 1,N-1が選ばれるまでに登場した数字の総数を求めよ
となる

答え = ΣΣt個取ったうえでxを取る場合
        t x
        
隣り合わないでa個取る場合にはすべてが等しい確率で含まれる…？
1234から2こ取る場合
1 3
1  4
 2 4
→違うわ　でも問題ない…？
t番目にxを取るの数を数え上げられればいい

→隣り合わないで x個取る方法 * x! * (N-1-x)!
→隣り合わないで x個取る通り数がわかればおk

dp[i][x] = i番目まで見てx個取る通り数
dp[i][x] = Σdp[j][x-1]
           j <= i-2

1つづつ置いていくことを考える
置くと置ける場所が2減る場合と1減る場合がある

最初はXこどこにでも置ける
そのうち、1減るのは2とおり、2減るのはN-2通り
次のおける集合を考える
1減るのは

=====答えを見た=====

愚直に考えればいい
各Kについて、K回目ですべて塗られているような順列の個数がわかればいい→f(K)
K回目に初めて塗られるのは f(K) - f(K-1) - f(K-2) - … - f(1)

f(K)を導出する
まず、K個のマシンを選びたい → g(K)とする
f(K) = g(K) * K! * (N-1-K)! である

g(K)を導出する
選ばれないマスはN-1-K個
隙間に選ばれないマスを入れていくことを考える

隙間はK-1個ある
ここにN-1-K個のあまりものを入れていく
nCr(K-1,N-1-K)

"""

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def modnCr(n,r,mod,fac,inv): #上で求めたfacとinvsを引数に入れるべし(上の関数で与えたnが計算できる最大のnになる)
    if n < r:
        return 0
    return fac[n] * inv[n-r] * inv[r] % mod

N = int(input())
mod = 10**9+7

fac,inv = modfac(N+10,mod)
fsum = 0
ans = 0

for K in range(1,N):
    f = modnCr(K-1,N-1-K,mod,fac,inv) * fac[K] * fac[N-1-K]
    ans += (f - fsum) * K % mod
    fsum = f
    fsum %= mod
    ans %= mod
print (ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())

M = 10**9+7 # 出力の制限
N = n+3 # 必要なテーブルサイズ

g1 = [None] * (N+1) # 元テーブル
g2 = [None] * (N+1) #逆元テーブル
inverse = [None] * (N+1) #逆元テーブル計算用テーブル
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M 

def cmb(n, r, M):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return (g1[n] * g2[r] * g2[n-r]) % M
ans = 0
prev = 0
# s = 0
for i in range((n+1)//2, n):
    tmp = (cmb(i-1, n-i-1, M) * g1[i] * g1[n-1-i])
    ans += tmp
#     ans += i*(tmp-prev)
    prev = tmp
#     print(i, tmp, g1[i], g1[n-1-i])
    ans %= M
i = n-1
ans = (i+1) * (cmb(i-1, n-i-1, M) * g1[i] * g1[n-1-i]) - ans
ans %= M
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())

M = 10**9+7 # 出力の制限
N = n+3 # 必要なテーブルサイズ

g1 = [None] * (N+1) # 元テーブル
g2 = [None] * (N+1) #逆元テーブル
inverse = [None] * (N+1) #逆元テーブル計算用テーブル
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M 

def cmb(n, r, M):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return (g1[n] * g2[r] * g2[n-r]) % M
ans = 0
prev = 0
# s = 0
for i in range((n+1)//2, n):
    tmp = (cmb(i-1, n-i-1, M) * g1[i] * g1[n-1-i])
    ans += i*(tmp-prev)
    prev = tmp
#     print(i, tmp, g1[i], g1[n-1-i])
    ans %= M
print(ans)

Submission status: Accepted

Solution code:
def cmb(n, r, mod):#コンビネーションの高速計算　
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

N=int(input())

res=0
W=0
for k in range((N-1)//2+1,N):
    res+=(g1[N-1-k]*g1[k]*cmb(k-1,N-k-1,mod)-W)*k
    res%=mod
    W=cmb(k-1,N-k-1,mod)*g1[k]*g1[N-1-k]

print(res)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
MOD = 10**9+7
def frac(limit):
    frac = [1]*limit
    for i in range(2,limit):
        frac[i] = i * frac[i-1]%MOD
    fraci = [None]*limit
    fraci[-1] = pow(frac[-1], MOD -2, MOD)
    for i in range(-2, -limit-1, -1):
        fraci[i] = fraci[i+1] * (limit + i + 1) % MOD
    return frac, fraci
frac, fraci = frac(1341398)
def comb(a, b):
    if not a >= b >= 0:
        return 0
    return frac[a]*fraci[b]*fraci[a-b]%MOD

N = int(readline())

f = [0]*N

for k in range(1, N):
    if 2*k < N:
        continue
    f[k] = comb(k-1, 2*k-N)

g = [f[i]*frac[i]*frac[N-1-i]%MOD for i in range(N)]

ans = 0

for k in range(1, N):
    ans = (ans + k*(g[k] - g[k-1]))%MOD

print(ans)

Submission status: Accepted

Solution code:
N=int(input())

mod=10**9+7

FACT=[1]
for i in range(1,10**6+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(10**6,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0

ANS=0
MINUS=0

def k_perm(k):
    return Combi(k-1,N-k-1)*FACT[k]*FACT[N-k-1]%mod

for k in range(N//2,N):
    ANS=(ANS+(k_perm(k)-k_perm(k-1))*k)%mod

print(ANS)

Submission status: Accepted

Solution code:
N=int(input())

mod=10**9+7

FACT=[1]
for i in range(1,10**6+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(10**6,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0

ANS=0
MINUS=0

def k_perm(k):
    return Combi(k-1,N-k-1)*FACT[k]*FACT[N-k-1]%mod

for k in range(N):
    ANS=(ANS+(k_perm(k)-k_perm(k-1))*k)%mod

print(ANS)

Submission status: Accepted

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

import numpy as np

MOD = 10**9 + 7

N = int(input())

def cumprod(arr):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

U = 10**6+100
x = np.arange(U,dtype=np.int64)
x[0] = 1
fact = cumprod(x)
x = np.arange(U,0,-1,dtype=np.int64)
x[0] = pow(int(fact[-1]),MOD-2,MOD)
fact_inv = cumprod(x)[::-1]

# 1,N-1の間のn台で完成させる方法
n = np.arange((N-3)//2,N-2)

# +1,+2をn+1個でN-2を作る方法
# +0,+1をn+1個でN-3-nを作る方法
# comb[n+1][N-3-n] * (n+2)! * (N-n-3)!
x = fact[n+1] * fact[n+2] % MOD * fact_inv[4-N+2*n] % MOD
answer = (x[-1] * (N-1) - x[:-1].sum()) % MOD
print(answer)

Submission status: Accepted

Solution code:
mod=10**9+7
N=int(input())
Fact=[1 for i in range(N+1)]
Finv=[1 for i in range(N+1)]
for i in range(N):
    Fact[i+1]=(Fact[i]*(i+1))%mod
Finv[N]=pow(Fact[N],mod-2,mod)
for i in range(N-1,-1,-1):
    Finv[i]=((i+1)*Finv[i+1])%mod
ans=0
SGL=[0 for i in range(N)]
for K in range(N):
    if 2*K-N<0:
        continue
    SGL[K]=(((Fact[K]*Finv[2*K-N])%mod)*Fact[K-1])
for K in range(1,N):
    ans+=((SGL[K]-SGL[K-1])*K)%mod
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
mod=10**9+7
fra=[1]*(n+2)
inv=[1]*(n+2)
t=1
for i in range(1,n+2):
    t*=i
    t%=mod
    fra[i]=t
t=pow(fra[n+1],mod-2,mod)
for i in range(n+1,0,-1):
    inv[i]=t
    t*=i
    t%=mod
ans=fra[n]
for i in range((n+1)//2,n):
    ans-=fra[i-1]*inv[2*i-n]*fra[i]%mod
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
mod=10**9+7
fra=[1]*(n+2)
inv=[1]*(n+2)
t1=1
t2=1
for i in range(1,n+2):
    t1*=i
    t1%=mod
    t2*=pow(i,mod-2,mod)
    t2%=mod
    fra[i]=t1
    inv[i]=t2
ans=fra[n]
for i in range((n+1)//2,n):
    ans-=fra[i-1]*inv[2*i-n]*fra[i]%mod
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
mod=10**9+7
N=int(input())

Factorial=[1]*(N+1)
for i in range(1,N+1):
  Factorial[i]=Factorial[i-1]*(i)%mod
def power(x,y):
  if y==0:
    return 1
  elif y==1:
    return x%mod
  elif y%2==0:
    return power(x,y//2)**2%mod
  else:
    return (power(x,y//2)**2)*x%mod

inverseFactorial=[1]*(N+1)
inverseFactorial[N]=power(Factorial[N],mod-2)
for i in range(0,N)[::-1]:
  inverseFactorial[i]=(inverseFactorial[i+1]*(i+1))%mod
  
def comb(x,y):
  if x<y or y<0:
    return 0
  else:
    return (Factorial[x]*inverseFactorial[y]*inverseFactorial[x-y])%mod

P=[0]*(N)
for k in range(N):
  P[k]=(comb(k-1,2*k-N)*Factorial[k]*Factorial[N-1-k])%mod
ans=0
for k in range(1,N):
  ans=(ans+k*(P[k]-P[k-1]))%mod
print(ans)

Submission status: Accepted

Solution code:
import sys
N=int(input())
if N==2:
    print(1)
    sys.exit()
if N==3:
    print(4)
    sys.exit()
mod=10**9+7
table=[1]*(N+3)
t=1
for i in range(1,N+3):
    t*=i
    t%=mod
    table[i]=t
rtable=[1]*(N+3)
t=1
for i in range(1,N+3):
    t*=pow(i,mod-2,mod)
    t%=mod
    rtable[i]=t
#print(table,rtable)
ans=0
l=0
for k in range(N):
    if 0>2*k-N:
        continue
    num=table[k]*table[N-1-k]
    div=table[k-1]*rtable[N-1-k]*rtable[k-1-(N-1-k)]
    div%=mod
    num*=div
    num%=mod
    ans+=k*(num-l)
    l=num
    l%=mod
    ans%=mod
    #print(k, num, div)
print(ans)

Submission status: Accepted

Solution code:
Md,MN=1000000007,1000006
fac,ifac,a,res,inv=[1,1],[1,1],[0],0,[1,1]
for i in range(2,MN):
    inv.append(inv[Md%i]*(Md-Md//i)%Md)
    fac.append(fac[-1]*i%Md)
    ifac.append(ifac[-1]*inv[i]%Md)
n=int(input())
for i in range(1,n):
    if i*2-n>=0:
        a.append(fac[i-1]*ifac[i+i-n]*fac[i]%Md)
    else:
        a.append(0)
for i in range(n-1,0,-1):
    a[i]=(a[i]-a[i-1])%Md
    res+=a[i]*i
res=res%Md
print(res)

Submission status: Accepted

Solution code:
Md,MN=1000000007,1000006
fac,ifac,a,res,inv=[1,1],[1,1],[0],0,[1,1]
for i in range(2,MN):
    inv.append(inv[Md%i]*(Md-Md//i)%Md)
    fac.append(fac[-1]*i%Md)
    ifac.append(ifac[-1]*inv[i]%Md)
def C(x,y):
    if(x<y):
        return 0
    return fac[x]*ifac[y]*ifac[x-y]
def D(x,y):
    return C(x-y+1,y)

n=int(input())
for i in range(1,n):
    if i*2-n>=0:
        a.append(D(n-3,n-i-1)*fac[i]*fac[n-i-1]%Md)
    else:
        a.append(0)
for i in range(n-1,0,-1):
    a[i]=(a[i]-a[i-1])%Md
    res=res+a[i]*i
res=res%Md
print(res)

Submission status: Accepted

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

list_size = 1000000

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

def power(n, x):
	if x == 1:
		return n
	elif x % 2 == 0:
		return power(int((n * n) % MOD), int(x / 2))
	else:
		return int((n * power(n, x - 1)) % MOD)

f_r_list[-1] = power(f_list[-1], MOD - 2)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % MOD)

def factorial(i):
	if i == 0:
		return 1
	else:
		return f_list[i-1]

def comb(n, r):
	if n < r:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

n = int(input())
ans = ((n - 1) * factorial(n - 1)) % MOD
for i in range(n - 2, (n + 1) // 2 - 1, -1):
	ans -= comb(i - 1, n - i - 1) * factorial(n - i - 1) * factorial(i)
	ans %= MOD
	#print(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
fn,fk,mod = [1]*n,[1]*n,10**9+7
for i in range(n-1): fn[i+1] = (fn[i]*(i+2))%mod
def power(n,k):
	if k==1: return n
	elif k%2==0: return power((n**2)%mod,k//2)
	else: return (n*power(n,k-1))%mod
def comb(n,k):
	if n<k or k<0: return 0
	elif k==0 or n==k: return 1
	else: return (((fn[n-1]*fk[n-k-1])%mod)*fk[k-1])%mod
fk[-1] = power(fn[-1],mod-2)
for i in range(2,n+1): fk[-i] = (fk[-i+1]*(n+2-i))%mod
fn.append(1)
ans = fn[n-2]*(n-1)
for i in range(n-2,(n-1)//2,-1):
	ans = (ans-comb(i-1,n-i-1)*fn[i-1]*fn[n-i-2])%mod
print(ans)

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect
 
def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]
 
MOD = 10**9 + 7
 
N = read()
 
NN = N + 1
fact = [1] * NN
for i in range(1, NN):
  fact[i] = (fact[i-1] * i) % MOD
 
def inv(n):
  return pow(n, MOD-2, MOD)
 
invfact = [0] * NN
invfact[-1] = inv(fact[-1])
for i in range(NN-2, -1, -1):
  invfact[i] = invfact[i+1] * (i+1) % MOD
 
def comb(n, k):
  return fact[n] * invfact[n-k] % MOD * invfact[k] % MOD
 
S = [0] * N
for k in range((N+1) // 2, N):
  S[k] = comb(k-1, N-1-k) * fact[k] % MOD * fact[N-1-k] % MOD
 
ans = 0
for k in range((N+1) // 2, N):
  ans = (ans + k * (S[k] - S[k-1]) % MOD) % MOD
print(ans)

Submission status: Accepted

Solution code:
def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    inverses = [1] * (n + 1)
    inverses[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        inverses[m - 1] = inv
    return factorials, inverses


def solve(n):
    MOD = 1000000007
    fac, inv = prepare(n, MOD)
    ans = 0
    cnt = 0
    for k in range((n + 1) // 2, n):
        tmp = fac[k - 1] * inv[n - 1 - k] * inv[2 * k - n]
        tmp %= MOD
        tmp *= fac[k]
        tmp %= MOD
        tmp *= fac[n - 1 - k]
        tmp %= MOD
        just = (tmp - cnt) % MOD
        ans += just * k
        ans %= MOD
        cnt = tmp
    return ans


n = int(input())
print(solve(n))

Submission status: Accepted

Solution code:
def C(n,m):return 0 if n<m else fact[n]*inv[m]%MOD*inv[n-m]%MOD
MOD=1000000007
n=int(raw_input())
fact=[1]*(n+1)
inv=[1]*(n+1)
for i in range(1,n+1):fact[i]=fact[i-1]*i%MOD
inv[n]=pow(fact[n],MOD-2,MOD)
for i in range(n,0,-1):inv[i-1]=inv[i]*i%MOD
ans=0
for i in range(1,n):ans+=C(i-1,n-i-1)*fact[i]%MOD*fact[n-i-1]%MOD
print(fact[n-1]*n-ans%MOD+MOD)%MOD

Submission status: Accepted

Solution code:
def C(n, m):
	return 0 if n < m else fact[n] * inv[m] % MOD * inv[n - m] % MOD

MOD = 1000000007
n = int(raw_input())
fact = [1] * (n + 1)
inv = [1] * (n + 1)
for i in range(1, n + 1):
	fact[i] = fact[i - 1] * i % MOD
inv[n] = pow(fact[n], MOD - 2, MOD)
for i in range(n, 0, -1):
	inv[i - 1] = inv[i] * i % MOD
ans = 0
for i in range(1, n):
	ans += C(i - 1, n - i - 1) * fact[i] % MOD * fact[n - i - 1] % MOD
print (fact[n - 1] * n - ans % MOD + MOD) % MOD

Submission status: Accepted

Solution code:
n = int(input())
p = 10**9 + 7

def fact(n, p):
    n_ = [1]
    for i in range(1, n+1):
         n_.append((n_[-1]*i) % p)
    return n_

def invfact(n, f, p):
    m = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        m.append(m[-1] * i % p)
    return m

ans = 0
m = n - 1
f = fact(m, p)
rf = invfact(m, f, p)
rf.reverse()
perm = 0

for k in range((n+1)//2, n):
    perm_ = f[k-1] * rf[2*k-n] %p * f[k] % p
    ans += (perm_ - perm) %p * k % p
    ans %= p
    perm = perm_

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
p = 10**9 + 7

def fact(n, p):
    n_ = 1
    yield n_
    for i in range(1, n+1):
         n_ = (n_*i) % p
         yield n_

def invfact(n, f, p):
    m = pow(f[n], p-2, p)
    yield m
    for i in range(n, 0, -1):
        m = m * i % p
        yield m

ans = 0
m = n - 1
f = list(fact(m, p))
rf = list(invfact(m, f, p))
rf.reverse()
perm = 0

for k in range((n+1)//2, n):
    perm_ = f[k-1] * rf[2*k-n] %p * f[k] % p
    ans += (perm_ - perm) %p * k % p
    ans %= p
    perm = perm_

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
p = 10**9 + 7

def fact(n):
    n_ = 1
    yield n_
    for i in range(1, n+1):
         n_ = (n_*i) % p
         yield n_

def invfact(n, f, p):
    m = pow(f[n], p-2, p)
    yield m
    for i in range(n, 0, -1):
        m = m * i % p
        yield m

ans = 0
m = n - 1
f = list(fact(m))
rf = list(invfact(m, f, p))
rf.reverse()
perm = 0

for k in range((n+1)//2, n):
    perm_ = f[k-1] * rf[2*k-n] %p * f[k] % p
    ans += (perm_ - perm) %p * k % p
    ans %= p
    perm = perm_

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
p = 10**9 + 7

def fact(n):
    n_ = 1
    yield n_
    for i in range(1, n+1):
         n_ = (n_*i) % p
         yield n_

def invfact(n, f, p):
    m = pow(f[n], p-2, p)
    yield m
    for i in range(n, 0, -1):
        m = m * i % p
        yield m

ans = 0
m = n - 1
f = list(fact(m))
rf = list(invfact(m, f, p))
rf.reverse()
perm = 0

for k in range((n+1)//2, n):
    b = m - k
    a = (m - 1) - (2 * b)
    perm_ = f[a+b] * rf[a] %p * f[k] % p
    ans += (perm_ - perm) %p * k % p
    ans %= p
    perm = perm_

print(ans)

Submission status: Accepted

Solution code:
def inv(x, mod = 10 ** 9 + 7):
    return pow(x, mod - 2, mod)

mod = 10 ** 9 + 7
N = int(input())
fact = [1]
for i in range(1, N):
    fact.append(fact[-1] * i % mod)
inv_fact = [inv(fact[-1])]
for i in reversed(range(1, N)):
    inv_fact.append(inv_fact[-1] * i % mod)
inv_fact = inv_fact[::-1]

ans = prev = 0
for k in range((N + 1) // 2, N):
    cnt = fact[k - 1] * inv_fact[k * 2 - N] % mod * fact[k] % mod
    ans += (cnt - prev + mod) * k
    ans %= mod
    prev = cnt
print(ans)

Submission status: Accepted

Solution code:
N = long(raw_input())
MOD = 10**9 + 7

fact = [1]*(N+1)

for i in range(1, N+1):
    fact[i] = r = i*fact[i-1] % MOD

cnts = [0]*(N+1)
rev = 1
for K in range(N-1, (N+1)/2-1, -1):
    cnts[K] = fact[K]*fact[K-1]*rev % MOD
    rev = rev * (2*K-N) * (2*K-N-1) % MOD

ans = 0
for K in range((N+1)/2, N):
    ans += (cnts[K] - cnts[K-1]) * K % MOD
    ans %= MOD
ans = (ans * pow(fact[N-2], MOD-2, MOD)) % MOD
print ans

Submission status: Accepted

Solution code:
N = int(input())
MOD = 10**9 + 7

fact = [1]*(N+1)

for i in range(1, N+1):
    fact[i] = r = i*fact[i-1] % MOD

cnts = [0]*(N+1)
rev = 1
for K in range(N-1, (N+1)//2-1, -1):
    cnts[K] = fact[K]*fact[K-1]*rev % MOD
    rev = rev * (2*K-N) * (2*K-N-1) % MOD

ans = 0
for K in range((N+1)//2, N):
    ans += (cnts[K] - cnts[K-1]) * K % MOD
    ans %= MOD
ans = (ans * pow(fact[N-2], MOD-2, MOD)) % MOD
print(ans)

Submission status: Accepted

Solution code:
# seishin.py
N = int(input())
MOD = 10**9 + 7

fact = [1]*(N+1)
rfact = [1]*(N+1)

for i in range(1, N+1):
    fact[i] = r = i*fact[i-1] % MOD
    rfact[i] = pow(r, MOD-2, MOD)

ans = cnt = 0
for K in range((N+1)//2, N):
    res = fact[K]*fact[K-1]*rfact[2*K-N] % MOD
    ans += (res - cnt) * K % MOD
    cnt = res
    ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


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

if N == 2:
    print(1)
    exit()
elif N == 3:
    print(4)
    exit()

kaijou = [1]
for i in range(1,N+1):
    kaijou.append((kaijou[-1]*i) % mod)

kaijou_inverse = [1]
for i in range(1,N+1):
    kaijou_inverse[i] = pow(kaijou[i],mod-2,mod)

def nCr(n,r):
    if n < r:
        return 0
    return (kaijou_inverse[n]*kaijou_inverse[r]*kaijou_inverse[n-r]) % mod

ans = 0
for i in range(1,N):
    ans += i*kaijou[i]*kaijou[N-i-i]*nCr(i-1,N-1-i)
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef long double ld;
typedef vector<ld> vd;
typedef bool bl;
typedef vector<bl> vb;
typedef unordered_map<ll,unordered_map<ll,ll>> graph;

const ll e5 = 1 << 20;
const ll mod = 1000000007;
const ll e3 = 1 << 13;
const ll INF = 1ll << 62;

ll factorial(ll n,ll mod = mod){
  static ll dp[e5];
  if(dp[n]) return dp[n];
  if(n == 0) return dp[n] = 1;
  return dp[n] = (n*factorial(n-1))%mod;
}

ll powl(ll x,ll r,ll mod = mod){
  ll ret = 1;
  for(;r != 0;r >>= 1){
    if(r&1 != 0) ret *= x,ret %= mod;
    x *= x,x %= mod;
  }
  return ret;
}

ll inverse(ll x,ll mod = mod){
  return powl(x,mod-2,mod);
}

ll combination(ll n,ll m,ll mod = mod){
  if(n < m) return 0;
  return (((factorial(n)*inverse(factorial(m)))%mod)*inverse(factorial(n-m)))%mod;
}


ll n;
ll ans = 0;

ll solve(ll k){
  return (((combination(k-1,n-1-k)*factorial(k))%mod)*factorial(n-1-k))%mod;
}


int main(){
  cin >> n;
  if(n == 2){
    cout << 1 << endl;
    return 0;
  }
  for(ll i = 2;i <= n-1;i++){
    ans += ((((solve(i)-solve(i-1)+mod)%mod)*i)%mod);
    ans %= mod;
  }
  cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef long double ld;
typedef vector<ld> vd;
typedef bool bl;
typedef vector<bl> vb;
typedef unordered_map<ll,unordered_map<ll,ll>> graph;

const ll e5 = 1 << 20;
const ll mod = 1000000007;
const ll e3 = 1 << 13;
const ll INF = 1ll << 62;

ll factorial(ll n,ll mod = mod){
  static ll dp[100000];
  if(dp[n]) return dp[n];
  if(n == 0) return dp[n] = 1;
  return dp[n] = (n*factorial(n-1))%mod;
}

ll powl(ll x,ll r,ll mod = mod){
  ll ret = 1;
  for(;r != 0;r >>= 1){
    if(r&1 != 0) ret *= x,ret %= mod;
    x *= x,x %= mod;
  }
  return ret;
}

ll inverse(ll x,ll mod = mod){
  return powl(x,mod-2,mod);
}

ll combination(ll n,ll m,ll mod = mod){
  if(n < m) return 0;
  return (((factorial(n)*inverse(factorial(m)))%mod)*inverse(factorial(n-m)))%mod;
}


ll n;
ll ans = 0;

ll solve(ll k){
  return (((combination(k-1,n-1-k)*factorial(k))%mod)*factorial(n-1-k))%mod;
}


int main(){
  cin >> n;
  if(n == 2){
    cout << 1 << endl;
    return 0;
  }
  for(ll i = 2;i <= n-1;i++){
    ans += ((((solve(i)-solve(i-1)+mod)%mod)*i)%mod);
    ans %= mod;
  }
  cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
from collections import defaultdict

N = int(input())

mod = 1000000007

def euclid(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)

_modinv = {}
def modinv(a):
    if a not in _modinv:
        inv, _, _ = euclid(a, mod)
        _modinv[a] = inv%mod
    return _modinv[a]

_factorial = {0: 1, 1: 1}
def factorial(n):
    if n not in _factorial:
        _factorial[n] = factorial(n-1)*n%mod
    return _factorial[n]

def comb(n, k):
    return factorial(n)*modinv(factorial(k))*modinv(factorial(n-k))%mod

if N == 2:
    print(1)
    exit()
if N == 3:
    print(4)

res = 0
mem = 0
    
for K in range((N+1)//2, N):
    tmp = factorial(K)*factorial(N-1-K)*comb(K-1, N-K-1)
    just = (tmp-mem)%mod
    mem = tmp
    res += K*just
    res %= mod
    
print(res)

Submission status: Runtime Error

Solution code:
n = int(input())
fn,fk,mod = [1]*n,[1]*n,10**9+7
for i in range(n-1): fn[i+1] = (fn[i]*(i+2))%mod
def power(n,k):
	if k==1: return n
	elif k%2==0: return power((n**2)%mod,k//2)
	else: return (n*power(n,k-1))%mod
def comb(n,k):
	if n<k or k<0: return 0
	elif k==0 or n==k: return 1
	else: return (((fn[n-1]*fk[n-k-1])%mod)*fk[k-1])%mod
fk[-1] = power(fn[-1],mod-2)
for i in range(2,n+1): fk[-i] = (fk[-i+1]*(n+2-i))%mod
fn.append(1)
ans = f[n-2]
for i in range(2,n):
	ans = (ans-comb(i-1,n-i-1)*fn[i-1]*fn[n-i-2])%mod
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
p = 10**9 + 7

def fact(n, p):
    n_ = [1]
    for i in range(1, n+1):
         n_.append((n_[-1]*i) % p)
    return n

def invfact(n, f, p):
    m = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        m.append(m[-1] * i % p)
    return m

ans = 0
m = n - 1
f = fact(m, p)
rf = invfact(m, f, p)
rf.reverse()
perm = 0

for k in range((n+1)//2, n):
    perm_ = f[k-1] * rf[2*k-n] %p * f[k] % p
    ans += (perm_ - perm) %p * k % p
    ans %= p
    perm = perm_

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
p = 10**9 + 7

# def fact(n, p):
#     n_ = 1
#     yield n_
#     for i in range(1, n+1):
#          n_ = (n_*i) % p
#          yield n_

# def invfact(n, f, p):
#     m = pow(f[n], p-2, p)
#     yield m
#     for i in range(n, 0, -1):
#         m = m * i % p
#         yield m

def fact(n, p):
    n_ = [1]
    for i in range(1, n+1):
         n_.append((n_[-1]*i) % p)
    return n

def invfact(n, f, p):
    m = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        m.append(m[-1] * i % p)
    return m

ans = 0
m = n - 1
f = fact(m, p)
rf = invfact(m, f, p)
rf.reverse()
perm = 0

for k in range((n+1)//2, n):
    perm_ = f[k-1] * rf[2*k-n] %p * f[k] % p
    ans += (perm_ - perm) %p * k % p
    ans %= p
    perm = perm_

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
p = 10**9 + 7

def fact(n, p):
    n_ = [1]
    for i in range(1, n+1):
         n_.append((n_[-1]*i) % p)
    return n

def invfact(n, f, p):
    m = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        m.append(m[-1] * i % p)
    return m

ans = 0
m = n - 1
f = list(fact(m, p))
rf = list(invfact(m, f, p))
rf.reverse()
perm = 0

for k in range((n+1)//2, n):
    perm_ = f[k-1] * rf[2*k-n] %p * f[k] % p
    ans += (perm_ - perm) %p * k % p
    ans %= p
    perm = perm_

print(ans)

Submission status: Runtime Error

Solution code:
from itertools import permutations
import collections
import numba
n = int(input())
machine = []
[machine.append(i) for i in range(n-1)]
result = []
for i in permutations(machine):
    l = []
    [l.append(i) for i in range(n)]
    score = 0
    for j in i:
        l[j] = -1
        l[j + 1] = -1
        score += 1
        if(all(x == -1 for x in l)):
            result.append(score)
            break
temp = collections.Counter(result)
ans = 0
for k,v in temp.items():
    ans += k*v
print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
from itertools import permutations
from numba import jit
import collections

n = int(input())
machine = []
for i in range(n-1):
    machine.append(i)
result = []
l = []
for i in permutations(machine):
    for _ in range(n):
        l.append(1)
    score = 0
    for j in i:
        l[j] = -1
        l[j + 1] = -1
        score += 1
        if(all(x == -1 for x in l)):
            result.append(score)
            l.clear()
            break
temp = collections.Counter(result)
ans = 0
for k,v in temp.items():
    ans += k*v
print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
from itertools import permutations
import collections
import numba

n = int(input())
machine = []
for i in range(n-1):
    machine.append(i)
result = []
l = []
for i in permutations(machine):
    for _ in range(n):
        l.append(1)
    score = 0
    for j in i:
        l[j] = -1
        l[j + 1] = -1
        score += 1
        if(all(x == -1 for x in l)):
            result.append(score)
            l.clear()
            break
temp = collections.Counter(result)
ans = 0
for k,v in temp.items():
    ans += k*v
print(ans%(10**9+7))