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

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

Solution (Python):

"""

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

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

for i in range((n+1)//2, n):
    tmp = (cmb(i-1, n-i-1, M) * g1[i] * g1[n-1-i])
    ans += tmp

    prev = tmp

    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)

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

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

    ans %= M
print(ans)

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

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

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

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

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


n = np.arange((N-3)//2,N-2)




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)

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

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

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

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

Solution (Python):
characteristic=10**9+7
def plus(input1,input2):
    return (input1+input2)%characteristic
def minus(input1,input2):
    return (input1-input2)%characteristic
def times(input1,input2):
    return (input1*input2)%characteristic
def exponen(input1,input2):
    return pow(input1,input2,characteristic)
def divide(input1,input2):
    return times(input1,exponen(input2,characteristic-2))
N=int(input())
Fact=[1 for i in range(N+1)]
Finv=[1 for i in range(N+1)]
for i in range(1,N+1):
    Fact[i]=times(Fact[i-1],i)
    Finv[i]=divide(1,Fact[i])
ans=0
SGL=[0 for i in range(N)]
for K in range(N):
    if 2*K-N<0:
        continue
    SGL[K]=times(times(Fact[K],Finv[2*K-N]),Fact[K-1])
for K in range(1,N):
    ans=plus(ans,times(SGL[K]-SGL[K-1],K))
print(ans)

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

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

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

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

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

Solution (Python):
N = int(input())

MOD = 10**9+7
fac = [1,1] + [0]*N
finv = [1,1] + [0]*N
inv = [0,1] + [0]*N
for i in range(2,N+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def ncr(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD

ans = 0
prev = 0
for k in range((N+1)//2, N):
    tmp = ncr(k-1, N-1-k) * fac[k] * fac[N-1-k]
    tmp %= MOD
    ans += (tmp - prev) * k
    ans %= MOD
    prev = tmp
print(ans)

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

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

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

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

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

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

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

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

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

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

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

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

Solution (Python):
P=10**9+7
def egcd(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)
def inv(x):
    return egcd(x,P)[0]
N=int(input())
Fact=[0 for i in range(N+1)]
Finv=[0 for i in range(N+1)]
Fact[0]=1
Finv[0]=1
for i in range(N):
    Fact[i+1]=((i+1)*Fact[i])%P
    Finv[i+1]=(Finv[i]*inv(i+1))%P
SGN=[0 for i in range(N)]
ans=0
for k in range(N):
    if 2*k-N>=0:
        SGN[k]=(((Fact[k-1]*Fact[k])%P)*Finv[2*k-N])%P
        ans=(ans+k*(SGN[k]-SGN[k-1]))%P
print(ans)

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

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

Solution (Python):

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)

Solution (Python):
N = int(input()) - 1

LARGE = 10**9+7

def ex_euclid(x, y):
    c0, c1 = x, y
    a0, a1 = 1, 0
    b0, b1 = 0, 1
 
    while c1 != 0:
        m = c0 % c1
        q = c0 // c1
 
        c0, c1 = c1, m
        a0, a1 = a1, (a0 - q * a1)
        b0, b1 = b1, (b0 - q * b1)
 
    return c0, a0, b0

fac_list = [1]*(N+1)
fac = 1
for i in range(1, N+1):
    fac = (fac * i) % LARGE
    fac_list[i] = fac
    
fac_inv_list = [1]*(N+1)
for i in range(N+1):
    fac_inv_list[i] =  pow(fac_list[i], LARGE-2, LARGE)
    
def nCr(n, r):
    return (((fac_list[n] * fac_inv_list[r]) % LARGE) * fac_inv_list[n-r]) % LARGE

def pat(n, r):
    return (((fac_list[n] * fac_inv_list[r]) % LARGE) * fac_inv_list[n-r]) % LARGE


pat = 0
score = 0

for k in range(N+1):
    if k-1 >= N-k:
        res = (((fac_list[k-1]*fac_list[k]) % LARGE) * fac_inv_list[k-1-N+k]) % LARGE
        score = (score + (res - pat) * k) % LARGE
        
        pat = res
print(score)

Solution (Python):


import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq



MOD = 10**9 + 7

def solve(f):
    n = f.read_int()

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

    def nCk(n, k):
        if k < 0 or k > n: return 0
        return (fact[n] * ifact[n-k] * ifact[k]) % MOD

    ans = 0
    c0 = 0
    for i in xrange(n/2,n):
        c1 = (nCk(i-1, n-1-i)*fact[i]*fact[n-i-1] - c0 + MOD) % MOD
        ans = (ans + c1*i) % MOD
        c0 = (c0 + c1) % MOD

    return ans


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case 
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)