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

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")
mod = 1000000007
inf = float('INF')
fact = [i for i in range(5 * 10 ** 5 + 1)]
fact[0] = 1
for i in range(5 * 10 ** 5):
    fact[i + 1] *= fact[i]
    fact[i + 1] %= mod
invfact = fact[:]
invfact[-1] = pow(invfact[-1], mod - 2, mod)
for i in range(5 * 10 ** 5, 0, -1):
    invfact[i - 1] = i * invfact[i]
    invfact[i - 1] %= mod

def combination_mod(n, k, mod=mod):
    """ power_funcを用いて(nCk) mod p を求める """ 
    """ nCk = n!/((n-k)!k!)を使用 """
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    a = fact[n]
    b = invfact[k]
    c = invfact[n - k]
    return (a * b * c) % mod

def nPk(a, b):
    return (fact[a] * invfact[a - b]) % mod

#solve
def solve():
    n, m = LI()
    ans = 0
    a = 1
    for i in range(n + 1):
        ans += nPk(m, i) * nPk(m - i, n - i) * nPk(m - i, n - i) * a * combination_mod(n, i) % mod
        ans %= mod 
        a *= - 1
    print(ans)
            
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
mod = int(1e9) + 7

g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

# 組み合わせ(1e9+7で割る場合)
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

# 順列(1e9+7で割る場合)
def pmt(n, r, mod):
    if (r < 0 or r > n):
        return 0
    return cmb(n, r, mod) * g1[r] % mod

if __name__ == "__main__":
    ans = 0
    for i in range(N+1):
        if i % 2 == 1:
            ans -= cmb(N, i, mod) * pmt(M, i, mod) * (pmt(M - i, N - i, mod))**2 % mod
        else:
            ans += cmb(N, i, mod) * pmt(M, i, mod) * (pmt(M - i, N - i, mod))**2 % mod
    print(ans % mod)

Submission status: Accepted

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

# 階乗
factorial = [1]
for i in range(1, M + 1):
    factorial.append(factorial[-1] * i % MOD)
inv_factorial = [-1] * (M + 1)
inv_factorial[-1] = pow(factorial[-1], MOD - 2, MOD)
for i in reversed(range(M)):
    inv_factorial[i] = inv_factorial[i + 1] * (i + 1) % MOD

ans = 0
for k in range(N + 1):
    ans += (
        factorial[N]
        * inv_factorial[k]
        * inv_factorial[N - k]
        * (-1) ** (k % 2)
        * factorial[M]
        * inv_factorial[M - k]
        * pow(factorial[M - k] * inv_factorial[M - N], 2, MOD)
    )
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

def mod_prepare(N):
    fac = [1, 1]
    finv = [1, 1]
    inv = [0, 1]
    for i in range(2, N + 1):
        fac.append(fac[i - 1] * i % mod)
        inv.append(mod - inv[mod % i] * (mod // i) % mod)
        finv.append(finv[i - 1] * inv[i] % mod)
    return fac, finv

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

fac, inv = mod_prepare(M)

ans = 0
sign = 1
for k in range(N + 1):
    ans += sign * fac[M - k] * inv[k] * inv[N - k]
    sign *= -1
    ans %= mod

print(ans * fac[N] * fac[M] * inv[M - N] * inv[M - N] % mod)

Submission status: Accepted

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

## nCkのmodを求める関数
# テーブルを作る(前処理)
max = 5 * 10**5 + 100
fac, finv, inv = [0]*max, [0]*max, [0]*max

def comInit(max):
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

    for i in range(2,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

comInit(max)

# 二項係数の計算
def com(n,k):
    if(n < k):
        return 0
    if( (n<0) | (k < 0)):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

cnt = [0] * (n+1)
tot = 0
for i in range(n,-1,-1):
    cnt[i] = com(n,i)*(fac[n-i])*com(m-i ,n-i)
    cnt[i] %= mod
    tot = cnt[i] - tot
    tot %= mod

ans = tot * fac[m] * finv[m-n]
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
#from functools import lru_cache

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,n,p=10**9+7):
    bi = str(format(n,"b"))#2進表現に
    res = 1
    for i in range(len(bi)):
        res = (res*res) %p
        if bi[i] == "1":
            res = (res*a) %p
    return res


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

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

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


if n == 1:
    print((m-n) * m % mod)
elif n == 2:
    ans = (m - n)**2 + (m - n + 1)
    for i in range(2):
        ans *= (m - i)
        ans %= mod
    print(ans)
else:
    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: Accepted

Solution code:
class nCrMod():
    def __init__(self, mod):
        self.mod = mod
        self.fac = [1, 1]
        self.finv = [1, 1]
        self.inv = [0, 1]

    def prep(self, n):
        mod = self.mod
        f, fi = self.fac[-1], self.finv[-1]
        for i in range(len(self.fac), n + 1):
            fn = f * i % mod
            v = -self.inv[mod % i] * (mod // i) % mod
            fin = fi * v % mod
            f, fi = fn, fin
            self.fac.append(f)
            self.finv.append(fi)
            self.inv.append(v)

    def __call__(self, n, r):
        if len(self.fac) <= n:
            self.prep(n)
        return self.fac[n] * self.finv[r] * self.finv[n - r] % self.mod


def main():
    N, M = map(int, input().split())
    mod = 10**9 + 7
    nCr = nCrMod(mod)
    nPr = lambda n, r: nCr(n, r) * nCr.fac[r] % mod
    r = nPr(M, N) ** 2 % mod
    for i in range(1, N + 1):
        r = (r + (-1)**i * nCr(N, i) * nPr(M, i) * (nPr(M - i, N - i) ** 2)) % mod
    return r % mod

print(main())

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
mod=10**9+7
framod=[1]
def framod_calc(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
        framod.append(a)

def permmod(n, k, mod):
    a=framod[n]
    c=framod[n-k]
    return (a * pow(c, mod-2, mod)) % mod

def combmod(n, k, mod):
    a=framod[n]
    b=framod[k]
    c=framod[n-k]
    return (a * pow(b, mod-2, mod) * pow(c, mod-2, mod)) % mod
framod_calc(m, mod)

a=combmod(m,n,mod)*framod[n]
a%=mod
b=0
for k in range(n+1):
    b+=((((-1)**k)*combmod(n,k,mod)*combmod(m-k,n-k,mod))%mod*framod[n-k])%mod
    b%=mod
print(a*b%mod)

Submission status: Accepted

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

MAXN = N+5
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+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 comb(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 = 1
for i in range(N):
    ans *= (M-i)
    ans %= MOD

ps = [1]
for i in range(N):
    ps.append((ps[-1] * (M-N+1+i)) % MOD)
ps.reverse()

tmp = 0
for i,p in enumerate(ps):
    t = p * comb(N,i)
    if i%2:
        t *= -1
    tmp += t

ans *= tmp
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
size = 500001
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: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,M=MI()
    
    ###################################
    #0~Nまで逆元などを事前計算
    def cmb(n, r, mod):
        if (r < 0) or (n < r):
            return 0
        r = min(r, n - r)
        return (fact[n] * factinv[r] * factinv[n-r])%mod

    fact=[1,1]
    factinv=[1,1]
    inv=[0,1]
    
    for i in range(2, max(N,M) + 3):
        fact.append((fact[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod // i)) % mod)
        factinv.append((factinv[-1] * inv[-1]) % mod)
    ###################################
    
    """
    Aは固定．
    
    「1つもない」は数え辛い，「少なくともk個ある」は数えやすい
    i=Piがk個以上ある
        kこ選ぶ：NCK
        残りを適当に並べる：(M-K)PK
        係数：(-1)^k
    
    """
    ans=0
    for k in range(N+1):
        cm=cmb(N,k,mod)
        rem=(fact[M-k]*factinv[M-N])%mod
        if k%2==0:
            c=1
        else:
            c=-1
        ans=(ans+c*cm*rem)%mod
        
    ans=(ans*fact[M]*factinv[M-N])%mod
    print(ans)
    
    


        
    

main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
mod=pow(10,9)+7
# n<=m
# コンビネーション、さらに高速。あらかじめO(N)の計算をすることでのちの計算が早くなる
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
g1=[1,1] # g1[i]=i! % mod
g2=[1,1] # g2[i]=(i!)^(-1) % mod
inverse=[0,1]
for i in range(2,m+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)

# 数列aの作り方
ans_a=g1[m]*g2[m-n]

# 数列bの作り方
ans_b=0
for i in range(n+1):
  tmp=cmb(n,i,mod)
  tmp*=(g1[m-i]*g2[m-n])%mod
  tmp%=mod
  ans_b+=tmp*(-1)**i
  ans_b%=mod
  #print(i,tmp,ans_b)

print((ans_a*ans_b)%mod)
#print(ans_a,ans_b)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
mod = 10**9+7
pos = [1]+[0]*M
neg = [1]+[0]*M
n = 1
for i in range(1, M+1):
    n = n*i%mod
    pos[i] = n
    neg[i] = pow(n, mod-2, mod)
ans = 0

def comb(n, r):
    return pos[n]*neg[r]*neg[n-r]%mod

# i個数字以上が被っている時の通り数
for i in range(N+1):
    ans += (-1)**i*comb(N, i)*pos[M]*neg[M-i]*(pow(pos[M-i]*neg[M-N], 2, mod))
    ans %= mod
print(ans)

Submission status: Accepted

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

n = N + M
fac = [1] * (n + 1) 
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = (fac[j - 1] * j) % MOD

inv[n] = pow(fac[n], MOD-2, MOD)
for j in range(n - 1, -1, -1):
    inv[j] = (inv[j + 1] * (j + 1)) % MOD

def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return (fac[n] * inv[n - r] * inv[r]) % MOD

def perm(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return comb(n, r) * fac[r] % MOD

ans = pow(perm(M, N), 2, MOD)
# r: AiとBiが一致する個数
for r in range(1, N + 1):
    p = comb(M, r) * perm(N, r) * pow(perm(M - r, N - r), 2, MOD) % MOD
    p *= -(-1) ** (r % 2)
    ans -= p
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:

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


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

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

def permute(n, k):
	return fact[n] * invfact[n - k] % MOD

def choose(n, k):
	return permute(n, k) * invfact[k] % MOD

total = pow(permute(M, N), 2, MOD)
add = -1

for i in range(1, N+1):
	total = (total + add * choose(N, i) * permute(M, i) * pow(permute(M-i, N-i), 2, MOD)) % MOD
	add *= -1

print(total)

Submission status: Accepted

Solution code:

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


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

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

def permute(n, k):
	return fact[n] * invfact[n - k] % MOD

def choose(n, k):
	return permute(n, k) * invfact[k] % MOD

total = pow(permute(M, N), 2, MOD)
add = -1

for i in range(1, N+1):
	total = (total + add * choose(N, i) * permute(M, i) % MOD * pow(permute(M-i, N-i), 2, MOD)) % MOD
	add *= -1

print(total)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
mod = 10**9 + 7
leng = 500010
fac = [1,1]
for i in range(2,500010):
    fac.append(fac[-1]*i%mod)

invfac = [0]*500010
invfac[500009] = pow(fac[500009],-1,mod)
for i in range(500009):
    invfac[500008-i] = invfac[500009-i]*(500009-i)%mod

def combi(n,m):
    return(fac[n]*invfac[m]*invfac[n-m]%mod)

def permu(n,m):
    return(fac[n]*invfac[n-m]%mod)

Ans = 0

for i in range(N+1):
    if i%2 == 0:
        Ans += combi(N,i)*permu(M,i)*(permu(M-i,N-i)**2)
    else:
        Ans -= combi(N,i)*permu(M,i)*(permu(M-i,N-i)**2)

print(Ans%mod)

Submission status: Accepted

Solution code:
'''
完全順列(derangement)
モンモール数(Montmort number)
'''

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

# 片方の順列の総数を求める
ans = 1
for i in range(N):
    ans *= M-i
    ans %= MOD

# M枚からN枚選ぶ完全順列を計算
d2, d1 = 1, M-N
d0 = d1
for i in range(2, N+1):
    # 1がk番目にある
    # 1番目にkがある
    d0 = (i-1)*d2 % MOD
    # 1番目にkがない
    d0 += (M-N+i-1)*d1
    d0 %= MOD
    d2, d1 = d1, d0

print(ans*d0 % MOD)

Submission status: Accepted

Solution code:
'''
完全順列(derangement)
モンモール数(Montmort number)
'''

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

# 片方の順列の総数を求める
ans = 1
for i in range(N):
    ans *= M-i
    ans %= MOD

# M枚からN枚選ぶ完全順列を計算
d = [1, M-N]
for i in range(2, N+1):
    # 1がk番目にある
    # 1番目にkがある
    t = (i-1)*d[-2] % MOD
    # 1番目にkがない
    t += (M-N+i-1)*d[-1] % MOD
    d.append(t)

print(ans*d[-1] % MOD)

Submission status: Accepted

Solution code:
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
mod = 10**9+7
N, M = map(int, readline().split())
 
fact = [1] * (M+1)
fact_inv = [1] * (M+1)
for i in range(1,M+1):
    fact[i] = fact[i-1] * i % mod 
fact_inv[M] = pow(fact[M],mod-2,mod)
for i in range(M,0,-1):
    fact_inv[i-1] = (i * fact_inv[i]) % mod 
 
def comb(n,r):
  return fact[n] * fact_inv[r] * fact_inv[n-r] % mod
total = 0
for k in range(N+1):
    a = fact[M-k] * fact_inv[M-N] * comb(N,k) % mod
    if k % 2 == 0:
        total += a
    else:
        total -= a
ans = (comb(M,N) * fact[N]) % mod * total 
print(ans%mod)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
table_len = 500010

fac = [1, 1]
for i in range(2, table_len):
    fac.append(fac[-1] * i % MOD)
    
finv = [0] * table_len
finv[-1] = pow(fac[-1], MOD - 2, MOD)
for i in range(table_len-1, -1, -1):
    finv[i-1] = finv[i] * i % MOD

def comb(n, k):
    return fac[n] * finv[k] * finv[n-k] % MOD

def perm(n, k):
    return fac[n] * finv[n-k] % MOD

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

print(sum( ((-1)**k * comb(N, k) * perm(M, k) * perm(M-k, N-k)**2 % MOD ) for k in range(N+1)) % MOD)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
table_len = 500010

fac = [1, 1]
for i in range(2, table_len):
    fac.append(fac[-1] * i % MOD)
    
finv = [0] * table_len
finv[-1] = pow(fac[-1], MOD - 2, MOD)
for i in range(table_len-1, -1, -1):
    finv[i-1] = finv[i] * i % MOD

def comb(n, k):
    return fac[n] * finv[k] * finv[n-k] % MOD

def perm(n, k):
    return fac[n] * finv[n-k] % MOD

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

print(sum( ((-1)**k * comb(N, k) * perm(M, k) * perm(M-k, N-k)**2 % MOD ) for k in range(N+1)) % MOD)

Submission status: Accepted

Solution code:
n, m = [int(x) for x in input().split(" ")]
MOD = int(1e9 + 7)


fact = [0 for _ in range(m + 1)]
fact[0] = 1
for i in range(1, m + 1):
    fact[i] = fact[i-1] * i % MOD

finv = [0 for _ in range(m + 1)]
finv[m] = pow(fact[m], MOD-2, MOD)
for i in range(m-1, -1, -1):
    finv[i] = finv[i+1] * (i + 1) % MOD

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

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

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

print(ans)

Submission status: Accepted

Solution code:
#高速化実験
class Combi():
    def __init__(self, N, mod):
        self.power = [1 for _ in range(N+1)]
        self.rev = [1 for _ in range(N+1)]
        self.mod = mod
        for i in range(2, N+1):
            self.power[i] = (self.power[i-1]*i) % self.mod
        self.rev[N] = pow(self.power[N], self.mod-2, self.mod)
        for j in range(N, 0, -1):
            self.rev[j-1] = (self.rev[j]*j) % self.mod

    def com(self, K, R):
        if K < R:
            return 0
        else:
            return ((self.power[K])*(self.rev[K-R])*(self.rev[R])) % self.mod

    def pom(self, K, R):
        if K < R:
            return 0
        else:
            return (self.power[K])*(self.rev[K-R]) % self.mod


def main():
    N, M = map(int, input().split())
    mod = 10**9+7
    c = Combi(5*10**5, mod)
    ans = c.pom(M, N)**2 % mod
    for k in range(1, N+1):
        s = (-1)**((k-1) % 2)
        t = c.com(N, k)
        u = c.pom(M-k, N-k)**2
        v = c.pom(M, k)
        ans -= s*t*u*v
        ans = ans % mod
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def comb(a, b):
    return fact[a] * pow(fact[a-b], mod-2, mod) * pow(fact[b], mod-2, mod) % mod
n, m = LI()
fact = [1] * (max(n, m) + 1)
for i in range(1, max(n, m)+1):
    fact[i] = i * fact[i-1]
    fact[i] %= mod

ret = 0
for x in range(n+1):
    if x % 2:
        ret -= comb(n, x) * fact[m-x] * pow(fact[m-x-(n-x)], mod-2, mod)
        ret %= mod
    else:
        ret += comb(n, x) * fact[m-x] * pow(fact[m-x-(n-x)], mod-2, mod)
        ret %= mod

ans = fact[m] * pow(fact[m-n], mod-2, mod) * ret
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
#test
class Combi():
    def __init__(self, N, mod):
        self.power = [1 for _ in range(N+1)]
        self.rev = [1 for _ in range(N+1)]
        self.mod = mod
        for i in range(2, N+1):
            self.power[i] = (self.power[i-1]*i) % self.mod
        self.rev[N] = pow(self.power[N], self.mod-2, self.mod)
        for j in range(N, 0, -1):
            self.rev[j-1] = (self.rev[j]*j) % self.mod

    def com(self, K, R):
        if K < R:
            return 0
        else:
            return ((self.power[K])*(self.rev[K-R])*(self.rev[R])) % self.mod

    def pom(self, K, R):
        if K < R:
            return 0
        else:
            return (self.power[K])*(self.rev[K-R]) % self.mod


def main():
    N, M = map(int, input().split())
    mod = 10**9+7
    c = Combi(5*10**5, mod)
    ans = c.pom(M, N)**2 % mod
    for k in range(1, N+1):
        s = (-1)**((k-1) % 2)
        t = c.com(N, k)
        u = c.pom(M-k, N-k)**2
        v = c.pom(M, k)
        ans -= s*t*u*v
        ans = ans % mod
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class Factorial:
    def __init__(self, max_fact, mod):
        #mod should be prime number
        #using homogeneous_product(n,r), max_fact ≧ max(n+r-1)
        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]
        self.mod = mod
        self.f = f
        self.fi = fi

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

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

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

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

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


max_fact = 5*10**5
mod = 10**9 + 7
fact_instance = Factorial(max_fact, mod)
comb = fact_instance.combination
perm = fact_instance.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: Accepted

Solution code:
class Factorial:
    def __init__(self, max_fact, mod):
        #mod should be prime number
        #using homogeneous_product(n,r), max_fact ≧ max(n+r-1)
        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]
        self.mod = mod
        self.f = f
        self.fi = fi

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

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

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

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

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


max_fact = 10**6
mod = 10**9 + 7
fact_instance = Factorial(max_fact, mod)
comb = fact_instance.combination
perm = fact_instance.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: Accepted

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

mod = 1000000007
fact = [1] * (m + 1)
ifact = [1] * (m + 1)

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


def comb(x, y):
    if y < 0 or y > x:
        return 0
    return (fact[x] * ifact[x - y] * ifact[y]) % mod


def perm(x, y):
    if y < 0 or y > x:
        return 0
    return (fact[x] * ifact[x - y]) % mod


ans = 0
for i in range(n + 1):
    ans += (-1) ** i * comb(n, i) % mod * perm(m, i) * (perm(m - i, n - i) % mod) ** 2
    ans %= mod
print(ans)

Submission status: Accepted

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

md=1000000007
fac=[0]*(M+1)
inv=[0]*(M+1)
ifac=[0]*(M+1)
inv[1]=1
for i in range(2,M+1):
	inv[i] = (md - (md//i) * inv[md%i] % md) % md;
fac[0]=1
ifac[0]=1
for i in range(1,M+1):
    fac[i]=fac[i-1]*i%md;
    ifac[i]=ifac[i-1]*inv[i]%md;

def choose(n,k):
    return fac[n]*ifac[k]*ifac[n-k]%md
def perm(m,n):
    return fac[m]*ifac[m-n]%md
ans=0
for k in range(N+1):
    if k%2==0:
        ans+=choose(N,k)*perm(M,k)*perm(M-k,N-k)**2
        ans%=md
    else:
        ans-=choose(N,k)*perm(M,k)*perm(M-k,N-k)**2
        ans%=md
print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M = map(int, readline().split())

    COM_MAX = M

    fac, finv, inv = [0] * (COM_MAX + 1), [0] * (COM_MAX + 1), [0] * (COM_MAX + 1)
    fac[0] = fac[1] = finv[0] = finv[1] = inv[1] = 1

    for i in range(2, COM_MAX + 1):
        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 com(n, r):
        if n < 0 or r < 0 or n < r:
            return 0
        return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD

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

    ans = 0
    for k in range(N + 1):
        tmp = perm(M - k, N - k) * com(N, k) % MOD
        if k & 1:
            tmp *= -1
        ans = (ans + tmp) % MOD

    ans = ans * perm(M, N) % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M = map(int, readline().split())

    COM_MAX = M

    fac, finv, inv = [0] * (COM_MAX + 1), [0] * (COM_MAX + 1), [0] * (COM_MAX + 1)
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

    for i in range(2, COM_MAX + 1):
        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 com(n, r):
        if n < 0 or r < 0 or n < r:
            return 0
        return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD

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

    ans = 0
    for k in range(N + 1):
        tmp = perm(M - k, N - k) * com(N, k) % MOD
        if k & 1:
            tmp *= -1
        ans = (ans + tmp) % MOD

    ans = ans * perm(M, N) % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
MOD = 10**9+7

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

kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]
 
gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]
 
def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

def nPr(n,r):
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

ans = 0
for i in range(N+1):
  ans += pow(-1,i,MOD) * nCr(N,i) * nPr(M,i) * ( nPr(M-i,N-i) )**2
  ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

class ModTools:
    """ 階乗・逆元用のテーブルを構築する """

    def __init__(self, MAX, MOD):

        # nCrならn、nHrならn+rまで作る
        MAX += 1
        self.MAX = MAX
        self.MOD = MOD
        # 階乗テーブル
        factorial = [1] * MAX
        factorial[0] = factorial[1] = 1
        for i in range(2, MAX):
            factorial[i] = factorial[i-1] * i % MOD
        # 階乗の逆元テーブル
        inverse = [1] * MAX
        # powに第三引数入れると冪乗のmod付計算を高速にやってくれる
        inverse[MAX-1] = pow(factorial[MAX-1], MOD-2, MOD)
        for i in range(MAX-2, -1, -1):
            # 最後から戻っていくこのループならMAX回powするより処理が速い
            inverse[i] = inverse[i+1] * (i+1) % MOD
        self.fact = factorial
        self.inv = inverse

    def nCr(self, n, r):
        """ 組み合わせ """

        if n < r: return 0
        # 10C7 = 10C3
        r = min(r, n-r)
        # 分子の計算
        numerator = self.fact[n]
        # 分母の計算
        denominator = self.inv[r] * self.inv[n-r] % self.MOD
        return numerator * denominator % self.MOD

    def nHr(self, n, r):
        """ 重複組み合わせ """

        # r個選ぶところにN-1個の仕切りを入れる
        return self.nCr(r+n-1, r)

    def nPr(self, n, r):
        """ 順列 """

        if n < r: return 0
        return self.fact[n] * self.inv[n-r] % self.MOD

N, M = MAP()

mt = ModTools(M+1, MOD)
acnt = mt.nPr(M, N)

bcnt = 0
for i in range(N+1):
    bcnt += mt.nCr(N, i) * mt.nPr(M-i, N-i) * (-1)**i
    bcnt %= MOD
ans = acnt * bcnt % MOD
print(ans)