Problem:


Score : 500 points

Problem Statement

Count the pairs of length-N sequences consisting of integers between 1 and M (inclusive), A_1, A_2, \cdots, A_{N} and B_1, B_2, \cdots, B_{N}, that satisfy all of the following conditions:

A_i \neq B_i, for every i such that 1\leq i\leq N.

A_i \neq A_j and B_i \neq B_j, for every (i, j) such that 1\leq i < j\leq N.

Since the count can be enormous, print it modulo (10^9+7).

Constraints

1\leq N \leq M \leq 5\times10^5

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M

Output

Print the count modulo (10^9+7).

Sample Input 1

2 2

Sample Output 1

2

A_1=1,A_2=2,B_1=2,B_2=1 and A_1=2,A_2=1,B_1=1,B_2=2 satisfy the conditions.

Sample Input 2

2 3

Sample Output 2

18

Sample Input 3

141421 356237

Sample Output 3

881613484



Sample input:
2 2


Sample output:
2

Submission status: Wrong Answer

Solution code:
import numpy as np
n,m=map(int,input().split())
mod=10**9+7
l=[0]*(n+2)
l[2]=1
for i in range(3,n+2):
    l[i]=((i-1)*(l[i-1]+l[i-2]))%mod
    
def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    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

mm,nn=prepare(m,mod) 
k=0
for i in range(min(n+1,m-n+1)):
    k+=(((mm[m-n]*nn[m-n-i]*nn[i])%mod)*(mm[n]*nn[n-i])%mod)%mod
    
    
    

print((((((l[n]*k)%mod)*mm[m])%mod)*nn[m-n])%mod)

Submission status: Wrong Answer

Solution code:
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]

N, M = ri_()
MOD = 10 ** 9 + 7
ans = 0
for i in range(N):
    ans = (ans * ((i * (M - i)) % MOD + ((M - 2 * i) * (M - i - 1)) % MOD)) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n,m=map(int,input().split())
mod=10**9+7
l=[0]*(n+2)
l[2]=1
for i in range(3,n+2):
    l[i]=((i-1)*(l[i-1]+l[i-2]))%mod
    
def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    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

mm,nn=prepare(m,mod) 
k=0
for i in range(min(n+1,m-n+1)):
    k+=(((mm[m-n]*nn[m-n-i]*nn[i])%mod)*(mm[n]*nn[i]*nn[n-i])%mod)%mod
    
    
    

print((((((l[n]*k)%mod)*mm[m])%mod)*nn[m-n])%mod)

Submission status: Wrong Answer

Solution code:
def nCr(n, r, mod):
    x, y = 1, 1
    for r_ in range(1, r+1):
        x = x*(n+1-r_)%mod
        y = y*r_%mod
    return x*pow(y, mod-2, mod)%mod

n, m = map(int, input().split())
mod = 10**9+7

res = 1
for i in range(1, n+1):
    res *= i
    res %= mod
print((((nCr(m, n, mod)*res)**2)//2)%mod)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
MOD = 10**9+7
def comb(n,r):
    res = 1
    fac = 1
    for i in range(r):
        res *= n-i
        res %= MOD
        fac *= i+1
        fac %= MOD
    return res*pow(fac,MOD-2,MOD)%MOD    

a = comb(m,n)
#print(a%MOD)

d = [1]*(5*10**5+1)
for i in range(1,n+1):
    d[i] = d[i-1]*(i+1)%MOD
print(d[n]%MOD * a%MOD)

Submission status: Wrong Answer

Solution code:
import numpy as np
n,m=map(int,input().split())
mod=10**9+7
l=[0]*(n+2)
l[2]=1
for i in range(3,n+2):
    l[i]=((i-1)*(l[i-1]+l[i-2]))%mod
    
def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    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

mm,nn=prepare(m,mod) 
k=((m-n)*n+1)%mod

print((((((l[n]*k)%mod)*mm[m])%mod)*nn[m-n])%mod)

Submission status: Wrong Answer

Solution code:
n, m = map(int,input().split())
mod = (10**9)+7;

chooseA = 1
val = m
for i in range(n):
	chooseA *= val
	chooseA %= mod
	val -= 1

p1 = pow(2, m-1, mod)

p1 = (chooseA + 1 - p1 + mod) % mod

chooseA *= p1
chooseA %= mod
print(chooseA)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
p = m*(m-1)
q = m**2 - 3*m + 3
a = p*(q**(n-1)) 
b = a % (10**9 +7)
print(b)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
mod=10**9+7
x=1
y=m
z=m-1
if n>m:
  print(0)
else:
  for i in range(n):
    x=(x*y)%mod
    y-=1
  for i in range(1,n):
    z=(z*(m-i-1)+i)%mod
  print(x*z%mod)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7
N,M = map(int,input().split())
ans1 = 1
for i in range(N):
    ans1 *= M - i
    ans1 %= MOD
ans2 = [1,M-N]
for i in range(2,N+1):
    ans2.append((ans2[-2] * (N-1) + ans2[-1] * (M-1))% MOD)
print(ans1 * ans2[N] % MOD)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7
N,M = map(int,input().split())
ans1 = 1
for i in range(N):
    ans1 *= M - i
    ans1 %= MOD
ans2 = [1,M-1]
for i in range(2,N+1):
    ans2.append((ans2[-2] * (N-1) + ans2[-1] * (M-1))% MOD)
print(ans1 * ans2[N] % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
MAX = 5*10**6 + 1

fact = [0 for _ in range(MAX)]
factinv = [0 for _ in range(MAX)]

fact[0] = 1
for k in range(1, MAX):
    fact[k] = fact[k - 1]*k
    fact[k] %= MOD

factinv[MAX - 1] = pow(fact[MAX - 1], MOD - 2, MOD)
for k in range(MAX - 1, 0, -1):
    factinv[k - 1] = fact[k]*k
    factinv[k - 1] %= MOD

def nCk(n, k):
    return fact[n]*factinv[k]*factinv[n - k] % MOD

def nPk(n, k):
    return fact[n]*factinv[n - k] % MOD

n, m = map(int, input().split(' '))

ans = 0
for k in range(n + 1):
    tmp = nCk(n, k)*nPk(m, k)*nPk(m - k, n - k)*nPk(m - k, n - k) % MOD
    if k % 2: ans += tmp
    else: ans -= tmp
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
mod = 10**9 + 7

fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, M + 1):
  fact.append((fact[-1] * i) % mod)
  inv.append((-inv[mod % i] * (mod // i)) % mod)
  factinv.append((factinv[-1] * inv[-1]) % mod)

ans = fact[M]*factinv[M-N]%mod #Aの選び方

y = [fact[M-N]]
x = factinv[N]*y[-1]%mod
for k in range(1, N):
  minus = 0
  for j in range(k):
    minus = (minus+fact[k]*factinv[k-j]%mod*factinv[j]%mod)%mod
  y.append((fact[M-N+k] - minus)%mod)
  x = (x+y[-1]*factinv[k]%mod*factinv[N-k]%mod)%mod
x = x*fact[N]%mod*factinv[M-N]%mod
print(ans*(ans-x)%mod)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())

mod = 10**9+7

fact = [1]
for i in range(1,5*10**5 + 1):
  fact.append((fact[-1]*i) % mod)
  
revfact = [1]
for i in range(1,5*10**5 + 1):
  revfact.append(pow(fact[i],mod-2,mod))

A = (fact[m]*revfact[n]*revfact[m-n]*fact[n]) % mod
B = 0
for i in range(n+1):
  tmp = (fact[n]*revfact[i]*revfact[n-i])*(fact[m-i]*revfact[n-i]*revfact[m-n])*fact[n-i]
  if i % 2 == 0:
    B += tmp
    B %= mod
  else:
    B -= tmp
    B %= mod
print((A*B) % mod)

Submission status: Time Limit Exceeded

Solution code:
from scipy.special import perm
from scipy.special import comb

n,m = map(int,input().split())

p = perm(m,n,exact=True)

d = [0]*n
d[0] += p
for i in range(1,n):
  d[i] += (perm(m,n-i,exact=True)*(perm(m-n+i,i,exact=True)**2) - sum(d[:i]))*comb(n,i,exact=True)

ans = (p**2 - sum(d[:n])) % (10**9 + 7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def p(n, k, mod):
  x = 1
  for ik in range(k):
    x *= (n - ik)
    x %= mod
  return x

MAX = 10 ** 9 + 7
def main():
  n, m = map(int, input().strip().split())
  s = 0
  nck = 1
  mpk = 1
  mkpnk = p(m, n, MAX)
  for k in range(0, n+1):
    if 0 < k <= n:
      nck *= (n - (k-1)) * pow(k, MAX-2, MAX) 
      nck %= MAX
    if 0 < k <= m:
      mpk *= (m - (k-1))
      mpk %= MAX
    if 0 < k <= n:
      mkpnk *= pow(m - (k - 1), MAX-2, MAX) 
      mkpnk %= MAX
    s += nck * ( (-1) ** k) * mpk * (mkpnk) ** 2
    s %= MAX
  print(s)
  

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
MAX = 5 * (10**5)
MOD = 10**9 + 7
def inv(p):
    q = MOD - 2
    res = 1
    while q:
        if q % 2 == 1:
            res = (res*p) % MOD
        p = (p*p) % MOD
        q //= 2
    return res

_fact = [0] * (MAX + 1)
_inv = [0] * (MAX + 1)
_fact[0] = 1
_inv[0] = 1
for k in range(1, MAX + 1):
    _fact[k] = _fact[k-1] * k % MOD
    _inv[k] = inv(_fact[k])

def P(m, n):
    return _fact[m] * _inv[m-n] % MOD

def C(m, n):
    return _fact[m] * _inv[m-n] * _inv[n] % MOD

def solve(n, m):
    res = 0
    for k in range(n+1):
        sign = 1 - 2 * (k%2)
        cur = sign * C(n, k) * P(m, k) * (P(m-k, n-k) ** 2)
        res = (res + cur) % MOD
    return res

n, m = map(int, input().split())
print(solve(n, m))

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
list=[0 for i in range(5*10**5+1)]
mod=10**9+7
list[0]=1
for i in range(len(list)-1):
  list[i+1]=list[i]*(i+1)%mod
def c(m,n):
  a=list[m]*pow(list[m-n],mod-2,mod)*pow(list[n],mod-2,mod)
  return a
def p(m,n):
  a=list[m]*pow(list[m-n],mod-2,mod)
  return a
ans=pow(p(M,N),2)
g=pow(list[M-N],mod-2,mod)
g2=pow(g,2,mod)
nn=list[N]
mm=list[M]
nmg=nn*mm*g2%mod
for i in range(1,N+1):
  ans+=nmg*pow(list[N-i],mod-2,mod)*pow(list[i],mod-2,mod)*list[M-i]*(-1)**i
  ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD=10**9+7
N, M = map(int, input().split())

FCT = [1]
for i in range(1, M+1):
    FCT.append((FCT[-1] * i)%MOD)

def pmu(n, r, mod=MOD):
    return (FCT[n] * pow(FCT[n-r], mod-2, mod)) % mod

def cmb(n, r, mod=MOD):
    return (pmu(n, r) * pow(FCT[r], mod-2, mod)) % mod

def solve():
    # {the num of case B when A=range(1,N+1)} x {permutation of A}
    # use inclusion-exclusion principle against former
    ans = 0
    for i in range(N+1):
        cp = (cmb(N, i) * pmu(M-i, N-i))%MOD
        ans = (ans + (1 if i%2==0 else -1) * cp) % MOD
    return (ans * pmu(M, N)) % MOD

if __name__ == "__main__":
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
def FACTORIAL(M):
    i = 1
    result = 1
    while True:
        result *= i
        if i >= M:
            break
        i+=1
    return result

def C(M, N):
    return int(P(M, N) / FACTORIAL(N))

def P(M, N):
    cumul = 1
    iter = 0

    while True:
        if iter >= N:
            break
        cumul = cumul*M
        M-=1
        iter+=1
    return cumul

def main():
    s = input().split()
    N = int(s[0])
    M = int(s[1])
    MOD = 1000000007
    x = P(M, N)

    result = x * x

    i = N
    while True:
        if i == N:
            y = C(N, i)
        elif i == M - 1:
            y = 0
        else:
            y = P(M-i-1, N-i) * C(N, i)

        result = result - x * y
        i -= 1
        if i == 0:
            break
    print(result % MOD)


main()

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
mod=10**9+7
f=[1]
for i in range(1,max(m,n)+1):f.append(f[i-1]*i%mod)
def comb(n,r):return f[n]*pow(f[r],mod-2,mod)*pow(f[n-r],mod-2,mod)%mod
def pern(n,r):return f[n]*pow(f[n-r],mod-2,mod)%mod
a=[0]*(n+1)
a[n]=1
for i in range(n-1,-1,-1):
    a[i]=(comb(n,n-i)*pern(m-i,n-i)-a[i+1])%mod
print(a[0]*pern(m,n)%mod)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
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 )

def nCr(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

def nPr(n,r):
    if not (0 <= r <= n):
        return 0
    return nCr(n, r) * g1[r] % mod


N,M=map(int,input().split())
ans=nPr(M,N)**2%mod
for i in range(1,N+1):
    p=nPr(M-i,N-i)**2%mod
    p=p*nPr(N,i)%mod
    p=p*nCr(M,i)%mod
    ans-=((-1) ** ((i % 2) ^ 1))*p
    ans%=mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    from numba import jit

    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    n, m = map(int, input().split())

    #output
    mod = pow(10, 9) + 7

    n_ = 5 * pow(10, 5) + 5
    fun = [1] * (n_+1)
    for i in range(1, n_+1):
        fun[i] = fun[i-1] * i % mod
    rev = [1] * (n_+1)
    rev[n_] = pow(fun[n_], mod-2, mod)
    for i in range(n_-1, 0, -1):
        rev[i] = rev[i+1] * (i+1) % mod
    @jit
    def cmb(n,r):
        if n < 0 or r < 0 or r > n: return 0
        return fun[n] * rev[r] % mod * rev[n-r] % mod
    @jit
    def perm(n, r):
        if n < 0 or r < 0 or r > n: return 0
        return fun[n] * rev[n-r] % mod

    #Aを1, 2, ..., nとする。
    #求める写像の総数をs(n, m)とする。
    #s(n, m) = sum(k=0, n)(cmb(n, k)* (-1)^k * cmb(m-k, n-k)*(n-k)!)

    import math
    answer = 0
    for i in range(n+1):
        temp = perm(n, i) * cmb(m, i) * pow(perm(m-i, n-i), 2)
        temp %= mod
        if i % 2 == 0:
            answer += temp
        else:
            answer -= temp
    print(answer % mod)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
list=[0 for i in range(5*10**5+1)]
mod=10**9+7
list[0]=1
for i in range(len(list)-1):
  list[i+1]=list[i]*(i+1)%mod
def c(m,n):
  a=list[m]*pow(list[m-n],mod-2,mod)*pow(list[n],mod-2,mod)
  return a
def p(m,n):
  a=list[m]*pow(list[m-n],mod-2,mod)
  return a
ans=p(M,N)**2
for i in range(1,N+1):
  ans+=c(N,i)*(-1)**i*p(M,i)*p(M-i,N-i)**2%mod
  ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from scipy.special import perm, comb

mod = 10 ** 9 + 7
N, M = map(int, input().split())

A = perm(M, N, exact=True) % mod

B = 0
for i in range(N + 1):
    B += (-1) ** i * comb(N, i, exact=True) * perm(M - i, N - i, exact=True) % mod

print(A * B % mod)

Submission status: Time Limit Exceeded

Solution code:
from scipy.special import perm, comb

mod = 10 ** 9 + 7
N, M = map(int, input().split())

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

A = perm(M, N, exact=True)

B = 0
for i in range(N + 1):
    B += (-1) ** i * cmb(N, i) * perm(M - i, N - i, exact=True)

print(A * B % mod)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
MOD = 10 ** 9 + 7


# 逆元の前計算
factorial = [1, 1]
inverse = [1, 1]
invere_base = [0, 1]
for i in range(2, N + M + 1):
    factorial.append((factorial[-1] * i) % MOD)
    invere_base.append((-invere_base[MOD % i] * (MOD // i)) % MOD)
    inverse.append((inverse[-1] * invere_base[-1]) % MOD)


def nCr(n, r):
    if not 0 <= r <= n:
        return 0
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


def nPr(n, r):
    if not 0 <= r <= n:
        return 0
    return nCr(n, r) * factorial[r] % MOD


ans = pow(nPr(M, N), 2, MOD)
for k in range(1, N + 1):
    x = nCr(M, k) * nPr(N, k) * pow(nPr(M - k, N - k), 2, MOD) % MOD
    if k % 2 == 1:
        x = -x
    ans += x
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007
fact = []
fact_inv = []
pow_ = []

def pow_ini(nn):
	global pow_
	pow_.append(nn)
	for j in range(62):
		nxt = pow_[j] * pow_[j]
		nxt %= mod
		pow_.append(nxt)
	return

def pow1(k):
    ansk = 1
    for ntmp in range(62):
        if((k >> ntmp) % 2 == 1):
            ansk *= pow_[ntmp]
            ansk %= mod
    return ansk

def fact_ini(n):
	global fact
	global fact_inv
	for i in range(n + 1):
		fact.append(0)
		fact_inv.append(0)
	fact[0] = 1
	for i in range(1, n + 1, 1):
		fact_tmp = fact[i - 1] * i
		fact_tmp %= mod
		fact[i] = fact_tmp
	pow_ini(fact[n])
	fact_inv[n] = pow1(mod - 2)
	for i in range(n - 1, -1, -1):
		fact_inv[i] = fact_inv[i + 1] * (i + 1)
		fact_inv[i] %= mod
	return

def nCm(n, m):
	assert(m >= 0)
	assert(n >= m)
	ans = fact[n] * fact_inv[m]
	ans %= mod
	ans *= fact_inv[n - m]
	ans %= mod
	return ans;

def nPm(n, m):
	assert(m >= 0)
	assert(n >= m)
	ans = fact[n]
	ans *= fact_inv[n - m]
	ans %= mod
	return ans;

fact_ini(5500000)
N, M = (int(x) for x in input().split())
ans = 0
for i in range(0, N+1, 1):
	anstmp = nCm(N, i) * nPm(M-i, N-i)
	anstmp %= mod
	if(i%2 == 1):
		anstmp *= -1
		anstmp += mod
		anstmp %= mod
	ans += anstmp
	ans %= mod
ans *= nPm(M, N)
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(5*(10**5)+10)
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

def pmt(n, r, p):
    return fact[n]*factinv[n-r]%p

p = 10 ** 9 + 7
N = 5*(10 ** 5) 
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
Q=[]
R=[]
S=[]
Q.append(0)
R.append(0)
S.append(0)
n,m = map(int,input().split())
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
def q(n,m,p):
    if n==1:
        return m-1
    else:
        sub=S[n]-R[n]
        for i in range(1,n):
            sub-=R[i]*Q[n-i]
        return sub
for j in range(1,n+1):
    R.append(cmb(n,j,p))
    S.append(pmt(m-n+j,j,p))
    Q.append(q(j,m-n+j,p))
print(int((S[n]*Q[n])%p))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(5*(10**5)+10)
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

def pmt(n, r, p):
    return fact[n]*factinv[n-r]%p

p = 10 ** 9 + 7
N = 5*(10 ** 5) 
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
Q=[]
R=[]
S=[]
Q.append(0)
R.append(0)
S.append(0)
n,m = map(int,input().split())
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
for i in range(1,n+1):
    R.append(cmb(n,i,p))
    S.append(pmt(m-n+i,i,p))
def q(n,m,p):
    if n==1:
        return m-1
    else:
        sub=S[n]-R[n]
        for i in range(1,n):
            sub-=R[i]*Q[n-i]
        return sub
for j in range(1,n+1):
    Q.append(q(j,m-n+j,p))
print(int((S[n]*Q[n])%p))

Submission status: Time Limit Exceeded

Solution code:
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

def pmt(n, r, p):
    return fact[n]*factinv[n-r]%p

p = 10 ** 9 + 7
N = 5*(10 ** 5) 
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
Q=[]
Q.append(0)
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
    
def q(n,m,p):
    if n==1:
        return m-1
    else:
        sub=pmt(m,n,p)-cmb(n,n,p)
        for i in range(1,n):
            sub-=cmb(n,i,p)*Q[n-i]
        return sub
n,m = map(int,input().split())
for j in range(1,n+1):
    Q.append(q(j,m-n+j,p))
print(int((pmt(m,n,p)*Q[n])%p))

Submission status: Time Limit Exceeded

Solution code:
import sys
import time
import math
from collections import deque
import heapq
import itertools
from decimal import Decimal
import bisect
from operator import itemgetter
MAX_INT = int(10e18)
MIN_INT = -MAX_INT
mod = 1000000000+7
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

import functools
@functools.lru_cache(maxsize=None)
def factrial_memo(n):
  fact = [1, 1]
  for i in range(2, n + 1):
    fact.append((fact[-1] * i) % mod)
  return fact

def permutation(n,r): #nPr
  return fact[n]*pow(fact[n-r],mod-2,mod)%mod
  
def combination(n,r): #nCr
  return permutation(n,r)*pow(fact[r],mod-2,mod)%mod

def homogeneous(n,r): #nHr
  return combination(n+r-1,r)%mod

def tami(n, r):
  if r == 0:
    res = fact[n]
    return res %mod
  elif r == 1:
    res = fact[n-1] * (n-1)
    return res %mod
  else:
    return tami(n-1, r-1) + tami(n-1, r-2)

N,M = IL()

fact = factrial_memo(10**6)

ans = 0
for i in range(max(0, 2*N-M), N+1):
  ans += combination(N,i) * combination(M-N, N-i) * tami(N, i) %mod
print(((combination(M, N) * fact[N] )%mod * ans) %mod)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
a = 1
MOD = 1000000007
d = [1] * (n + 1)
for i in range(n):
  d[i+1] = ((m - n + i) * d[i] + i * d[i-1]) % MOD
  a *= (m - i) % MOD
print(a * d[n] % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7

MOD_t_MAX = 5*10**5+10

fac  = [None] * MOD_t_MAX
finv = [None] * MOD_t_MAX
inv  = [None] * MOD_t_MAX
def MOD_COM_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MOD_t_MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD
def MOD_COM(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

def MOD_perm(n, r):
    rtn = 1
    for _ in range(r):
        rtn *= n
        rtn %= MOD
        n -= 1
    return rtn

def MOD_inv(a):
    b = MOD
    u = 1
    v = 0
    while b > 0:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u = u % MOD
    if u < 0:
        u += MOD
    return u

def main():
    n, m = map(int, input().split())
    ans = 0
    perm = MOD_perm(m, n)
    MOD_COM_init()
    for i in range(n+1):
        tmp = perm * MOD_COM(n, i) % MOD
        ans += (-1)**i * tmp
        ans %= MOD
        perm *= MOD_inv(m-i)
        perm %= MOD
    print(ans*MOD_perm(m, n)%MOD)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def permutation(n, x, mod=10**9+7):
    # nPx
    # 順列
    # ex) permutaion(5, 2) = 20
    tmp = 1
    for i in range(n, n-x, -1):
        tmp = (tmp * i) % mod
    return tmp

def power_func(a,b,p=10**9+7):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

n,v=map(int,input().split())
m=10**9+7
perm1=deque([1])
perm2=deque([permutation(v,n)])
comb=deque([1])
ones=deque([1])
acc=((comb[-1]*perm1[-1]%m)*perm2[-1]**2)%m
for k in range(n):
  #nCk+1=nCk*(n-k/k+1)
  comb.append((comb.pop()*(n-k)*power_func(k+1,m-2))%m)
  #vPk+1=vPk*(v-k)
  perm1.append((perm1.pop()*(v-k))%m)
  #v-(k+1)Pn-(k+1)=v-kPn-k/(v-k)
  perm2.append((perm2.pop()*power_func(v-k,m-2))%m)
  #(-1)^k+1=(-1)^k*(-1)
  ones.append(ones.pop()*(-1))
  acc+=ones[-1]*((comb[-1]*perm1[-1]%m)*perm2[-1]**2)%m
print(acc%m)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
MOD = (10**9) + 7

a = 10 ** 7 + 10 ** 6
fact = [0] * a
fact[0] = 1
for i in range(1, a):
    fact[i] = fact[i-1] * i % MOD

inv_fact = [0] * a
inv_fact[a-1] = pow(fact[a-1], MOD-2, MOD)
for i in range(a-1, 0, -1):
    inv_fact[i-1] = inv_fact[i] * i % MOD


def nCk(n, k):
    return (fact[n] * inv_fact[k] * inv_fact[n-k]) % MOD


def nPk(n, k):
    return (fact[n] * inv_fact[n-k]) % MOD


ans = 0
for i in range(N+1):
    tmp = nCk(N, i) * nPk(M, i) * (nPk(M-i, N-i))**2 % MOD
    if i % 2 == 0:
        ans += tmp
    else:
        ans -= tmp
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

fact = [1, 1]
for i in range(2, 5 * 10 ** 5 + 5):
    fact.append((i * fact[-1]) % MOD)


def main():
    k, n = (int(x) for x in input().split())
    ans = (C(n, k) * fact[k]) % MOD
    ans = ans * (ans - sum(
        (-1) ** (i + 1) * ((C(k, i) * C(n - i, k - i)) % MOD * fact[k - i]) % MOD for i in range(1, k + 1)))
    ans %= MOD
    print(ans)


def C(n, k):
    if n < k:
        return 0
    if n == k or k == 0:
        return 1
    return (fact[n] * inv(fact[k] * fact[n - k])) % MOD


def inv(k):
    return pow(k, MOD - 2, MOD)


main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
#from heapq import heappop, heappush
#from collections import OrderedDict, defaultdict
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
from collections import deque
#import numba

def generate_inv(n,mod):
    """
    逆元行列
    n >= 2
    Note: mod must bwe a prime number
    """
    ret = [0, 1]
    for i in range(2,n+1):
        next = -ret[mod%i] * (mod // i)
        next %= mod
        ret.append(next)
    return ret

def generate_comb_m_i(M, inv, mod):
    ret = [1, M]
    for i in range(2, M+1):
        tmp = (ret[-1] * (M-(i-1)) * inv[i]) % mod
        ret.append(tmp)
    return ret
def generate_p_N_i(N, mod):
    ret = [1]
    for i in range(1, N+1):
        tmp = (ret[-1] * (N - (i-1))) % mod
        ret.append(tmp)
    return ret

def generate_p_mi_ni(M, N, mod):
    ret = deque([1])
    cache = deque([1])
    for i in range(1, N+1):
        tmp = (cache[0] * (M-N+i)) % mod
        cache.appendleft(tmp)
        ret.appendleft((tmp ** 2) % mod)
    return ret


def run():
    N, M = map(int, input().split())
    mod = 10 ** 9 + 7

    inv = generate_inv(M, mod)

    comb_m_i = generate_comb_m_i(M, inv, mod)
    #print(comb_m_i[0])
    p_N_i = generate_p_N_i(N, mod)
    #print(p_N_i[0])
    p_mi_ni = generate_p_mi_ni(M, N, mod)
    #print(p_mi_ni[0])

    ret = p_mi_ni[0]

    sub = 0
    for i in range(1, N+1):
        tmp = (comb_m_i[i] * p_N_i[i] * p_mi_ni[i]) % mod
        tmp *= (i%2) * 2 - 1
        tmp %= mod
        sub += tmp

    ret -= sub
    ret %= mod

    print(ret)

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
#from heapq import heappop, heappush
#from collections import OrderedDict, defaultdict
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
from collections import deque
#import numba

def generate_inv(n,mod):
    """
    逆元行列
    n >= 2
    Note: mod must bwe a prime number
    """
    ret = [0, 1]
    for i in range(2,n+1):
        next = -ret[mod%i] * (mod // i)
        next %= mod
        ret.append(next)
    return ret

def generate_comb_m_i(M, inv, mod):
    ret = [1, M]
    for i in range(2, M+1):
        tmp = ret[-1]
        tmp *= M-(i-1)
        tmp %= mod
        tmp *= inv[i]
        tmp %= mod
        ret.append(tmp)
    return ret
def generate_p_N_i(N, mod):
    ret = [1]
    for i in range(1, N+1):
        tmp = ret[-1] * (N - (i-1))
        tmp %= mod
        ret.append(tmp)
    return ret

def generate_p_mi_ni(M, N, mod):
    ret = deque([1])
    cache = deque([1])
    for i in range(1, N+1):
        tmp = cache[0]
        tmp *= M-N+i
        tmp %= mod
        cache.appendleft(tmp)
        ret.appendleft((tmp ** 2) % mod)
    return ret


def run():
    N, M = map(int, input().split())
    mod = 10 ** 9 + 7

    inv = generate_inv(M, mod)

    comb_m_i = generate_comb_m_i(M, inv, mod)
    #print(comb_m_i[0])
    p_N_i = generate_p_N_i(N, mod)
    #print(p_N_i[0])
    p_mi_ni = generate_p_mi_ni(M, N, mod)
    #print(p_mi_ni[0])

    ret = p_mi_ni[0]

    sub = 0
    for i in range(1, N+1):
        tmp = (comb_m_i[i] * p_N_i[i] * p_mi_ni[i]) % mod
        tmp *= (i%2) * 2 - 1
        tmp %= mod
        sub += tmp

    ret -= sub
    ret %= mod

    print(ret)

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
#from heapq import heappop, heappush
#from collections import OrderedDict, defaultdict
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
from collections import deque
#import numba

def generate_inv(n,mod):
    """
    逆元行列
    n >= 2
    Note: mod must bwe a prime number
    """
    ret = [0, 1]
    for i in range(2,n+1):
        next = -ret[mod%i] * (mod // i)
        next %= mod
        ret.append(next)
    return ret

def generate_comb_m_i(M, inv, mod):
    ret = [1, M]
    for i in range(2, M+1):
        tmp = ret[-1]
        tmp *= M-(i-1)
        tmp %= mod
        tmp *= inv[i]
        tmp %= mod
        ret.append(tmp)
    return ret
def generate_p_N_i(N, mod):
    ret = [1]
    for i in range(1, N+1):
        tmp = ret[-1] * (N - (i-1))
        tmp %= mod
        ret.append(tmp)
    return ret

def generate_p_mi_ni(M, N, mod):
    ret = deque([1])
    cache = deque([1])
    for i in range(1, N+1):
        tmp = cache[0]
        tmp *= M-N+i
        tmp %= mod
        cache.appendleft(tmp)
        ret.appendleft((tmp ** 2) % mod)
    return ret


def run():
    N, M = map(int, input().split())
    mod = 10 ** 9 + 7

    inv = generate_inv(M, mod)

    comb_m_i = generate_comb_m_i(M, inv, mod)
    #print(comb_m_i[0])
    p_N_i = generate_p_N_i(N, mod)
    #print(p_N_i[0])
    p_mi_ni = generate_p_mi_ni(M, N, mod)
    #print(p_mi_ni[0])

    ret = p_mi_ni[0]

    sub = 0
    for i in range(1, N+1):
        tmp = (comb_m_i[i] * p_N_i[i]) % mod
        tmp = (tmp * p_mi_ni[i]) % mod
        tmp *= (i%2) * 2 - 1
        tmp %= mod
        sub += tmp

    ret -= sub
    ret %= mod

    print(ret)

if __name__ == "__main__":
    run()