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

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=[]
R=[]
S=[]
Q.append(0)
R.append(0)
S.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)
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
n,m = map(int,input().split())
for j in range(1,n+1):
    Q.append(q(j,m-n+j,p))
print(int((S[n]*Q[n])%p))

Submission status: Runtime Error

Solution code:
fac=[1]*505050
inv=[1]*505050
finv=[1]*505050
mod=1000000007
for i in range(1,500010):
  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 C(n,r):
  if n<0 or r<0 or n<r: return 0
  return fac[n]*inv[n-r]*inv[r]%mod

n,m=map(int,input().split())
ans=0
for i in range(N+1):
  ans+=C(n,i)*fac[M]*finv[M-i]*(C(M-i,N-i)**2)*(1 if i%2==0 else -1) % mod
print(ans%mod)

Submission status: Runtime Error

Solution code:
fac=[0]*505050
inv=[0]*505050
finv=[0]*505050
mod=1000000007
fac[0]=finv[0]=inv[1]=1
for i in range(1,500010):
  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 C(n,r):
  if n<0 or r<0 or n<r: return 0
  return fac[n]*inv[n-r]*inv[r]%mod

n,m=map(int,input().split())
ans=0
for i in range(N+1):
  ans+=C(n,i)*fac[M]*finv[M-i]*(C(M-i,N-i)**2)*(1 if i%2==0 else -1) % mod
print(ans%mod)

Submission status: Runtime Error

Solution code:
fac=[0]*505050
inv=[0]*505050
finv=[0]*505050
mod=1000000007
fac[0]=finv[0]=inv[1]=1;
for i in range(1,500010):
  fac[i]=fac[i-1]*i%mod
  inv[i]=inv[mod%i]*(mod//i)%mod
  finv[i]=finv[i-1]*inv[i]%mod

def C(n,r):
  if n<0 or r<0 or n<r: return 0
  return fac[n]*inv[n-r]*inv[r]%mod

n,m=map(int,input().split())
ans=0
for i in range(N+1):
  ans+=C(n,i)*fac[M]*finv[M-i]*(C(M-i,N-i)**2)*(1 if i%2==0 else -1) % mod
print(ans%mod)

Submission status: Runtime Error

Solution code:
SIZE=4*10**5+1; MOD=10**9+7 #998244353 #ここを変更する
 
SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
fac = [0]*SIZE  # fac[j] = j! mod MOD
finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
    inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD
 
def choose(n,r): # nCr mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0
 
def chofuku(n,r): # nHr mod MOD の計算
    return choose(n+r-1,r)

def narabekae(n,r): #nPr mod MOD の計算
    return fac[n]*finv[n-r]%MOD


N,M=map(int,input().split())
ans=0
for k in range(N+1):
    ans+=choose(N,k)*narabekae(M-k,N-k)*(-1 if k%2==1 else 1)
    ans%=MOD
ans*=narabekae(M,N)

print(ans%MOD)

Submission status: Runtime Error

Solution code:
SIZE=4*10**5+1; MOD=10**9+7 #998244353 #ここを変更する
 
SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
fac = [0]*SIZE  # fac[j] = j! mod MOD
finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
    inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD
 
def choose(n,r): # nCr mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0
 
def chofuku(n,r): # nHr mod MOD の計算
    return choose(n+r-1,r)

def narabekae(n,r): #nPr mod MOD の計算
    return fac[n]*finv[n-r]%MOD


N,M=map(int,input().split())
ans=0
for k in range(N+1):
    ans+=choose(N,k)*narabekae(M-k,N-k)*(-1 if k%2==0 else 1)
    ans%=MOD
ans*=narabekae(M,N)

print(ans%MOD)

Submission status: Runtime Error

Solution code:
SIZE=4*10**5+1; MOD=10**9+7 #998244353 #ここを変更する
 
SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
fac = [0]*SIZE  # fac[j] = j! mod MOD
finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
    inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD
 
def choose(n,r): # nCr mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0
 
def chofuku(n,r): # nHr mod MOD の計算
    return choose(n+r-1,r)

def narabekae(n,r): #nPr mod MOD の計算
    return fac[n]*finv[n-r]%MOD


N,M=map(int,input().split())
ans=0
for k in range(N+1):
    ans+=choose(N,k)*narabekae(M-k,N-k)*((-1)**k)
    ans%=MOD
ans*=narabekae(M,N)

print(ans%MOD)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
mem = defaultdict(lambda : None)
mem[(0,0,0)] = 0
def dp(a,b,s):
  if mem[(a,b,s)] is not None:
    return mem[(a,b,s)]
  x = a&1
  y = b&1
  xor = s&1
  res = float("inf")
  if x^y != xor:
    mem[(a,b,s)] = res
    return res
  else:
    res = 2*dp(a>>1,b>>1,s>>1)
    if a > 1:
      pants = 2*dp((a-1)>>1,(b+1)>>1,s>>1)+1
      if pants < res:
        res = pants
  mem[(a,b,s)] = res
  return res

n = int(input())
a = list(map(int, input().split()))
s = 0
for i in a[2:]:
  s ^= i
b = a[1]
a = a[0]
ans = dp(a,b,s)
if ans == float("inf"):
  ans = -1
print(ans)

Submission status: Runtime Error

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

dp = [0] * n
mod = 10**9 + 7

dp[0] = m - n
dp[1] = (m - n)**2 + (m - n + 1)


for i in range(2, n):
    dp[i] = (dp[i-1] + dp[i-2]) * i + dp[i-1] * (m - n)
    dp[i] %= mod

ans = dp[-1]

for i in range(n):
    ans *= (m - i)
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
m=10**9+7
#r!(0>r>M)
lis=[0]
for q in range(1,n+1):
  lis.append(lis[-1]*q%m)
from functools import lru_cache
@lru_cache(maxsize=1000)
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p

@lru_cache(maxsize=1000)
def power_func(a,b,p):
  """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
acc=0
for j in range(n+1):
  s=comb(n,j,m)
  t=s*(factorial(m)//factorial(j))%m
  acc+=((-1)**j)*t*(factorial(m-j)//factorial(n-j))**2%m
print(acc%m)

Submission status: Runtime Error

Solution code:
size = 500000
mod = 10 ** 9 + 7
fac = [0] * size
finv = [0] * size
inv = [0] * size

fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2, size):
    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 nPr(n, r, mod):
    if n < 0 or r < 0 or n < r:
        return 0
    return fac[n] * finv[n-r] % mod

g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, size + 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, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

N, M = map(int,input().split())

ans = 0
flag = 1

for k in range(N+1):
    ans += flag * nPr(M - k, N - k, mod) * nCr(N, k, mod) * nPr(M, N, mod)
    flag *= -1
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
x=0
for a in A:
    x^=a
ans=''
for a in A:
    ans+=str(x^a)+' '
print(ans)

Submission status: Runtime Error

Solution code:
def makefac(n):
    global faclist
    faclist = [1, 1]
    for i in range(2, n + 1):
        faclist.append(faclist[-1] * i % MOD)
    return None
def mcomb(n, r):#nCr % MOD
    return faclist[n] * pow(faclist[r], -1, MOD) * pow(faclist[n-r], -1) % MOD
def mperm(n, r):#nPr % MOD
    return faclist[n] * pow(faclist[n-r], -1, MOD)

N, M = map(int, input().split())
MOD = 10 ** 9 + 7
makefac(M)
ans = mperm(M, N)
for k in range(1, N + 1):
    ans += ((-1)**k * mcomb(N, k) * mperm(M - k, N - k)) % MOD
ans = ans * mperm(M, N) % MOD
print(ans)

Submission status: Runtime Error

Solution code:
max_fact = 5 * 10**5
mod = 10**9 + 7

f = [1] * (max_fact + 1)
for idx in range(2, max_fact + 1):
    f[idx] = f[idx - 1] * idx
    f[idx] %= mod
fi = [pow(f[-1], mod - 2, mod)]
for idx in range(max_fact, 0, -1):
    fi += [fi[-1] * idx % mod]
fi = fi[::-1]

def factorial(self, n):
    return f[n]

def factorial_inverse(self, n):
    return fi[n]

def combination(self, n, r):
    return f[n] * fi[r] * fi[n - r] % mod

def permutation(self, n, r):
    return f[n] * fi[n - r] % mod

def homogeneous_product(self, n, r):
    return f[n + r - 1] * fi[r] * fi[n - 1] % mod


comb = combination
perm = permutation

N, M = [int(_) for _ in input().split()]
ans = 0
for p in range(N + 1):
    ans += (-1)**p * comb(N, p) * perm(M - p, N - p)
    ans %= mod
ans *= perm(M, N)
ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
#解説方針
#標準入力
n, m = map(int, input().split())
#逆元
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):
    if (r < 0) or (n < r):
        return 0
    #r = min(r, n - r)
    return fact[n] * factinv[n - r] % p
  
p = 10 ** 9 + 7
N = n + 1
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, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

#print(pmt(3, 2, p))
#(-1)**K * (NCK) * (MPK) * (M-KPN-K)**2をKについて足し合わせる
ans = 0
for i in range(n + 1):
  a = (-1) ** i
  b = cmb(n, i, p)
  c = pmt(m, i, p)
  d = pmt(m - i, n - i, p)
  #print(a, b, c, d)
  ans += a * b * c * (d ** 2)
  
print(ans)

Submission status: Runtime Error

Solution code:
M=10**9+7
n,m=map(int,input().split())
import sys, functools as ft
sys.setrecursionlimit(10**18)
@ft.lru_cache(None)
def f(n):
  if n<2: return 1
  return n*f(n-1)%M
a=0
for k in range(n+1):
  a+=(-1)**k*f(m-k)*pow(f(k)*f(n-k),-1,M)%M
print(a*f(n)*f(m)*pow(f(m-n)**2,-1,M)%M)

Submission status: Runtime Error

Solution code:
M=10**9+7
n,m=map(int,input().split())
import sys, functools as ft
sys.setrecursionlimit(10**9)
@ft.lru_cache(None)
def f(n):
  if n<2: return 1
  return n*f(n-1)%M
a=0
for k in range(n+1):
  a+=(-1)**k*f(m-k)*pow(f(k)*f(n-k),-1,M)%M
print(a*f(n)*f(m)*pow(f(m-n)**2,-1,M)%M)

Submission status: Runtime Error

Solution code:
M=10**9+7
n,m=map(int,input().split())
import sys, functools as ft
sys.setrecursionlimit(10**6)
@ft.lru_cache(None)
def f(n):
  if n<2: return 1
  return n*f(n-1)%M
a=0
for k in range(n+1):
  a+=(-1)**k*f(m-k)*pow(f(k)*f(n-k),-1,M)%M
print(a*f(n)*f(m)*pow(f(m-n)**2,-1,M)%M)

Submission status: Runtime Error

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

def comb(n, r, mod):
    if r<0 or r>n:
        return 0
    r = min(r, n-r)
    return fac[n] * (finv[r] * finv[n-r] % mod) % mod

def perm(n, r, mod):
    if r<0 or r>n:
        return 0
    return (fac[n] * finv[n-r]) % mod

fac = [1, 1]
finv = [1, 1]
inv = [0, 1]
for i in range(2, max(N + 1, M + 1)):
    fac.append((fac[-1] * i) % mod)
    inv.append((-inv[mod%i] * (mod//i)) % mod)
    finv.append((finv[-1] * inv[-1]) % mod)
for i in range(N+1):
    ans += (-1)**i * ((comb(N, i, mod) * perm(M, i, mod))%mod * (perm(M-i, N-i, mod)**2)%mod)%mod
    ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
import random
from decimal import Decimal
import itertools
import re
import bisect
from collections import deque, Counter
from functools import lru_cache

sys.setrecursionlimit(10**9)
INF = 10**13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
def SERIES(n): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ')
def GRID(h,w): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ').reshape(h,-1)[:,:w]
def GRIDfromString(h,w): return np.frombuffer(sys.stdin.buffer.read(), 'S1').reshape(h,-1)[:,:w]
MOD = 1000000007

class Combination():
    def __init__(self, max_n, mod):
        self.fact = [1, 1]
        self.factinv = [1, 1]
        self.inv = [0, 1]
        self.mod = mod

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

    def get_permu(self,n, r):
        return self.get_value(n,r)*self.fact[r]

    def get_value(self, n, r):
        if r < 0 or n < r:
            return 0
        r = min(r, n-r)
        return self.fact[n] * self.factinv[r] * self.factinv[n-r] % self.mod


def main():
	n, m = LI()
	comb = Combination(5*10**5,MOD)
	ans = 0
	for k in range(n+1):
		ans += (-1)**k * comb.get_value(n,k) *  comb.get_permu(m,k) * comb.get_permu(m-k,n-k)**2
		ans %= MOD
	print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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

dp = [0 for _ in range(n+1)]
dp[1] = m - n
for i in range(2, n+1):
    dp[i] = dp[i-1] * i + fac[i-1] * (i-1)
    dp[i] %= mod


ans = dp[n]

tmp = m
for _ in range(n):
    ans *= tmp
    ans %= mod
    tmp -= 1

print(ans)1

Submission status: Runtime Error

Solution code:
N=int(input())
print(sum((N//i)*(N//i+1)//2)*i for i in range(1,N+1))

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split(" "))
a_number = 1
for i in range(m+1-n,m+1):
  a_number *= i % (10**9+7)

dp = [0 for i in range(n)]
dp[1] = 1
for i in range(2, n):
  dp[i] = (n-1)*(dp[i-1]+dp[i-2])% (10**9+7)

dp2 = [0 for i in range(m-n+1)]
dp2[0] = dp[n-1]
for i in range(m-n):
  dp2[i+1] = (dp2[i]+dp2[i]*n)% (10**9+7)
  
print(a_number*dp2[m-n]% (10**9+7))

Submission status: Runtime Error

Solution code:
N, M = list(map(int, input().split()))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

print(int(pow(permutations_count(M, N),2)//2)%(10**9+7))

Submission status: Runtime Error

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

def comb(N, A, MOD):
    num = reduce(lambda x, y: x * y % MOD, range(N, N - A, -1))
    den = reduce(lambda x, y: x * y % MOD, range(1, A + 1))
    return num * pow(den, MOD - 2, MOD) % MOD

a = 1
for i in range(1, n+1):
    a *= i
    a %= mod

print((comb(m, n, mod) * comb(m, n, mod) - a)%mod))

Submission status: Runtime Error

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

nA = 1

for i in range(N):
  nA *= M - i
  nA %= mod_

dp = [0 for i in range(N+1)]
dp[1] = M - N
dp[2] = M - N + 1 + (M - N)*(M - N)
dp[1] %= mod_
dp[2] %= mod_
for i in range(3, N+1):
  dp[i] = dp[i-1] * (M - N + i - 1) + dp[i-2] * (i-1)
  dp[i] %= mod_
  
print( nA * dp[N] % mod_ )

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split())
MOD = 10**9 + 7
a = 1
for i in range(N):
  a *= M-i
  a %= MOD
 
#nCr求める
def inv(a):
  return pow(a,MOD-2,MOD)

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

def choose(n,r):
  if r==0 or r==n:
    return 1
  else:
    return fact[n]*inv(fact[r])*inv(fact[n-r])%MOD
  
print(a*(N*choose(N,M)-1)%MOD)

Submission status: Runtime Error

Solution code:
## coding: UTF-8
MOD = 10**9+7
MAX = 5*(10**5)
N, M = map(int,input().split())



laslas = 0
last = 1
mon = [0, 1]

for i in range(2, MAX+10):
    now = (i-1) * (laslas + last)
    now %= MOD
    mon.append(now)
    laslas = last
    last = now


mpn = 1
now = M
for i in range(N):
    mpn *= now
    mpn %= MOD
    now -= 1

if(M>N):
    m_1pn = 1
    now = M-1
    for i in range(N):
        m_1pn *= now
        m_1pn %= MOD
        now -= 1

if(M>N):
    ans = (mon[N-1] * m_1pn)
    ans %= MOD
    ans *= mpn
    ans %= MOD
else:
    ans = mod[N-1]*mpn
    ans %= MOD
print(ans)

Submission status: Runtime Error

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

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    def make_factorial_table(size, mod):
        '''
        fact_mod[i] は i! % mod を表す。fact_mod[0] ~ fact_mod[size] まで計算可能なテーブルを返す
        >>> make_factorial_table(20, 10**9+7)
        [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 227020758, 178290591, 674358851, 789741546, 425606191, 660911389, 557316307, 146326063]
        '''
        fact_mod = [1] * (size + 1)
        for i in range(1, size + 1):
            fact_mod[i] = (fact_mod[i - 1] * i) % mod
        return fact_mod
    

    def combination(n, r, mod, fact_table):
        '''
        フェルマーの小定理 
        a ^ p-1 ≡ 1 (mod p)
        a ^ p-2 ≡ 1/a (mod p) (逆元)
        nCr = (n!) / ((n-r)! * r!) だが、mod p の世界ではこの分母を逆元を用いて計算しておくことが可能
        
        >>> m = 1000000007
        >>> fact_table = make_factorial_table(100, m)
        >>> combination(10, 5, m, fact_table)
        252
        >>> combination(100, 50, m, fact_table)
        538992043
        '''
        numerator = fact_table[n]
        denominator = (fact_table[n-r] * fact_table[r]) % mod
        # pow はすでに繰り返し二乗法で効率的に実装されている
        return (numerator * pow(denominator, mod-2, mod)) % mod
    

    n, m = mi()
    f = make_factorial_table(10**6)
    ans = (combination(m, n, mod, f) * f[n]) % mod
    tmp = 0
    for k in range(m-n):
        pattern = (pow(n - 1, n - k, mod) * f[k]) % mod
        tmp = (tmp + pattern) % mod
    print((ans * tmp) % mod)

        
        


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N, M = map(int,input())
MOD = 10**9 + 7
a = 1
for i in range(N):
  a *= M-i
  a %= MOD
 
#nCr求める
def inv(a):
  return pow(a,MOD-2,MOD)

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

def choose(n,r):
  if r==0 or r==n:
    return 1
  else:
    return fact[n]*inv(fact[r])*inv(fact[n-r])%MOD
  
print(a*(N*choose(N,M)-1)%MOD)

Submission status: Runtime Error

Solution code:
import math
mod = 10**9+7
n, m = map(int,input().split())
P = [math.factorial(m-n+1)/math.factorial(m-n)]*n
Q = [0, 1]
for i in range(1,n):
  P[i] = P[i-1]*(m-n+i+1)%mod
for j in range(2, n):
  Q[j] = (j-1)(Q[j-1]+Q[j-2])%mod
if m == 1:
  print(0)
else:
  print(P[-1]*(Q[-1]+(m-n)*n%mod)%mod)

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()


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

n,m = na()
# mCn~mCm
ans = 1
for i in range(m-n+1,m):
    ans = ans*i%mod

for i in range(0,n-m):
    ans = ans*cmb(n,i,mod)%mod
    for j in range(n-i,n-1):
        ans = ans*j%mod

print(ans)

Submission status: Runtime Error

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+3):
    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,m-n)):
    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: Runtime Error

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

def comb(N, A, MOD):
    num = reduce(lambda x, y: x * y % MOD, range(N, N - A, -1))
    den = reduce(lambda x, y: x * y % MOD, range(1, A + 1))
    return num * pow(den, MOD - 2, MOD) % MOD

a = 1
for i in range(1, N+1):
    a *= i
    a %= mod

print((comb(m, n, mod) * comb(m, n, mod) - (a*comb(m, n, mod)%mod)%mod))

Submission status: Runtime Error

Solution code:
import math

N, M = map(int, input().split())

n = math.factorial(M-N)
m = math.factorial(M)

res = int(m * m / n / n / 2)

res %= 10 ** 9 + 7

print(res)

Submission status: Runtime Error

Solution code:
from functools import lru_cache
@lru_cache(maxsize=None)
def main():
    import math
    n,m = map(int,input().split())
    ans = 0

    for i in range(0,n+1):
        ans+=(math.factorial(m-i)*math.factorial(n)/(math.factorial(i)*math.factorial(n-i)**2))
    
    print(int(ans+0.001))

main()

Submission status: Runtime Error

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

from functools import reduce
from operator import mul
from collections import defaultdict, Counter
from heapq import heappush, heappop
import sys
from math import sqrt, floor

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")


def debug(*x):
    print(*x)


def solve(N):
    "void()"
    px = [0] * (N + 1)
    primes = []
    divs = defaultdict(list)
    divs[1] = []

    for i in range(2, N + 1):
        if px[i] == 0:
            # prime
            primes.append(i)
#            divs[i] = [i]
            j = 2 * i
            while j <= N:
                px[j] = 1
                j += i

    # debug("num primes: len(primes)", len(primes))
    # 664579

    # numdivs = [0] * (N + 1)
    # numdivs[1] = 1
    # for i in range(2, N + 1):
    #     if not i in divs:
    #         ubound = floor(sqrt(i)) + 1
    #         for p in primes:
    #             if p > ubound:
    #                 break
    #             if i % p == 0:
    #                 divs[i] = [p] + divs[i // p]
    #                 break

    #     numdivs[i] = reduce(
    #         mul,
    #         (x + 1 for x in Counter(divs[i]).values()),
    #         1)

    # print(sum(i * numdivs[i] for i in range(1, N+1)))
    numdivs = [0] * (N + 1)
    numdivs[1] = 1
    #targets = [1]
    for p in primes:
        ubound = N // p
        for t in range(N, 0, -1):
            if t > ubound:
                continue
            if numdivs[t] == 0:
                continue
            cur = t
            cur *= p
            m = 2
            tnum = numdivs[t]
            while cur <= N:
                # debug(": cur", cur)
                numdivs[cur] = tnum * m
                m += 1
                # targets.append(cur)
                cur *= p
            # print(targets)
    # debug(": numdivs", numdivs)
    print(sum(i * numdivs[i] for i in range(1, N+1)))


def main():
    N = int(input())
    solve(N)


def _test():
    """
    >>> solve(4)
    23

    >>> solve(100)
    26879

    #>>> solve(10000000)
    #838627288460105
    """
    # solve(100000)  # 1m8.507s
    # solve(10000000)
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

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

from functools import lru_cache
@lru_cache(None)
def dfs(i, parent_kosu):
    alpha = (parent_kosu*pow(m-i-1,2, p))%p
    beta  = (parent_kosu*(m-i))%p

    if i == n-1:
        return (alpha+beta)%p

    return dfs(i+1,(alpha+beta)%p)%p

alpha = (m*(m-1))%p
ans = dfs(1,alpha)

print(ans)

Submission status: Runtime Error

Solution code:
def choose(n,a,mod):
    x, y = 1, 1
    for i in range(a):
        x = x * (n - i) % mod
        y = y * (i + 1) % mod
    return x * pow(y, mod - 2, mod) % mod

n,m = map(int,input().split())
ans = 0
mod = pow(10**9+7)
for i in range(n+1):
    if i == 0:
        stand = choose(m,n,mod)
        ans += stand
        k = 1
    else:
        k*=i
        k %= mod
        stand *= (-1)*n*pow(m,mod-2,mod)
        stand %= mod
        ans += pow(k,mod-2,mod)*stand
        ans %= mod
ans *= k
ans %= mod
print(ans)