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

Solution (Python):

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


N, M = map(int, input().split())
mod = 10**9+7
c = Combi(10**6, 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) % mod
    v = c.pom(M, k) % mod
    ans -= s*t*u*v
print(ans % mod)

Solution (Python):
N,M=map(int,input().split())
mod = 10**9+7
def fact_list(a):
  ans = [1]
  for i in range(1,a+1):
    ans.append(ans[-1]*i % mod)
  return ans

factlist = fact_list(M)

def comb_mod(a,b):
  return (factlist[a]*pow(factlist[b],mod-2,mod)*pow(factlist[a-b],mod-2,mod) )% mod

def permu_mod(a,b):
  return (factlist[a]*pow(factlist[a-b],mod-2,mod) % mod)

ans = 0
for i in range(N+1):
  ans += comb_mod(N,i)*(-1)**i*permu_mod(M,i)*permu_mod(M-i,N-i)**2 
  ans = ans % mod
print(ans)

Solution (Python):
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

class CombMod:
	def __init__(self, N):
		facts = [1]
		rfacts = [1]
		for i in range(1, N+1):
			facts.append(facts[i-1]*i % mod)
			rfacts.append(pow(facts[i], mod-2, mod))
		self.facts = facts
		self.rfacts = rfacts

	def comb(self, n, k):
		return self.facts[n]*self.rfacts[k]*self.rfacts[n-k] % mod

	def perm(self, n, k):
		return self.facts[n]*self.rfacts[n-k] % mod

	def fact(self, k):
		return self.facts[n] % mod

	def rfact(self, k):
		return self.rfacts[n] % mod

N, M = rl()
cm = CombMod(M)

ans = 0
for i in range(0, N+1):
	ans += (-1)**i * cm.perm(M, i) * (cm.perm(M-i, N-i)**2) * cm.comb(N, i)
	ans = ans % mod
print(ans)

Solution (Python):
def e_neq(MOD=10**9 + 7):
    N, M = [int(i) for i in input().split()]

    class Combination(object):
        """素数 mod に対する二項係数の計算"""
        __slots__ = ['mod', 'fact', 'factinv']

        def __init__(self, argmax: int = 10**6, mod: int = 10**9 + 7):
            fac, inv = [1], []
            fac_append, inv_append = fac.append, inv.append

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

            inv_append(pow(fac[-1], -1, mod))
            for i in range(argmax, 0, -1):
                inv_append((inv[-1] * i) % mod)

            self.mod, self.fact, self.factinv = mod, fac, inv[::-1]

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

        def permutation(self, n, r):
            return self.combination(n, r) * self.fact[r] % self.mod

    c = Combination(M)
    comb, perm = c.combination, c.permutation
    return sum(comb(N, k) * (-1)**k * perm(M, k) * perm(M - k, N - k)**2 for k in range(N + 1)) % MOD

print(e_neq())

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

f = [1, 1]
f_inv = [1, 1]
inv = [0, 1]
 
for i in range(2, m+1):
    f.append((f[-1] * i ) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    f_inv.append((f_inv[-1] * inv[-1]) % mod)

def comb(n, k):
    return f[n] * f_inv[k] * f_inv[n-k] % mod

def per(n, k):
    return f[n] * f_inv[n-k] % mod

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

print(ans)

Solution (Python):



mod = 10**9+7               
N = 10**6                   
g1 = [1]*(N+1)              
g2 = [1]*(N+1)              
for i in range(2, N + 1 ): 
    g1[i] = ( g1[i-1] * i ) % mod
g2[N] = pow(g1[-1], mod-2, mod)
for i in range(N, 0, -1):
    g2[i-1] = ( g2[i] * i ) % 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 ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % mod

def main():
    N, M = map(int, input().split())
    ret = 0
    for k in range(N+1):
        tmp = nCr(N, k) * nPr(M, k) * (nPr(M-k, N-k)**2) % mod
        if k%2==0:
            ret += tmp
        else:
            ret -= tmp
        ret %= mod
    print(ret)

if __name__ == '__main__':
    main()

Solution (Python):
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

class CombMod:
	def __init__(self, N):
		self.fact = [1]
		self.rfact = [1]
		for i in range(1, N+1):
			self.fact.append(self.fact[i-1]*i % mod)
			self.rfact.append(pow(self.fact[i], mod-2, mod))

	def comb(self, n, k):
		return self.fact[n]*self.rfact[k]*self.rfact[n-k] % mod

	def perm(self, n, k):
		return self.fact[n]*self.rfact[n-k] % mod

N, M = rl()
cm = CombMod(M)

ans = 0
for i in range(0, N+1):
	ans += (-1)**i * cm.perm(M, i) * (cm.perm(M-i, N-i)**2) * cm.comb(N, i)
	ans = ans % mod
print(ans)

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

fact = [1] * (M+1)
fact_inv = [1] * (M+1)
for i in range(1, M+1):
    fact[i] = i * fact[i-1] % mod
fact_inv[M] = pow(fact[M], mod-2, mod)
for i in range(1, M+1)[::-1]:
    fact_inv[i-1] = i * fact_inv[i] % mod
comb = lambda n, k: fact[n] * fact_inv[k] * fact_inv[n-k] % mod

ans = comb(M, N) * fact[N] % mod
for k in range(1, N+1):
    ans += (-1)**k * comb(N, k) * fact[M-k] * fact_inv[M-N] % mod
    ans %= mod
ans = ans * comb(M, N) * fact[N] % mod
print(ans)

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

Solution (Python):
MOD=10**9+7
fac=[1]+[0]*(5*(10**5))
rev_fac=[0]*(5*(10**5)+1)
for i in range(1,len(fac)):
    fac[i]=(fac[i-1]*i)%MOD
rev_fac[-1]=pow(fac[-1],MOD-2,MOD)
for i in range(len(rev_fac)-2,-1,-1):
    rev_fac[i]=(rev_fac[i+1]*(i+1))%MOD
N,M=map(int,input().split())
ans=0
for k in range(N+1):
    ans=(ans+pow(-1,k)*fac[N]*rev_fac[k]*rev_fac[N-k]*fac[M]*rev_fac[M-k]*((fac[M-k]*rev_fac[M-N])**2))%MOD
print(ans)

Solution (Python):

import sys

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip() 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

    
def main():
    n,m = na()
    mod = 1000000007
    ans = 0
    pm = 1
    nCk = 1
    tmp = 1
    for i in range(m-n+1,m+1):
        tmp *= i*i
        tmp %= mod
    for k in range(n+1):
        ans += pm*nCk*tmp
        ans %= mod
        pm *= -1
        nCk *= (n-k)*pow(k+1,mod-2,mod)
        nCk %= mod
        tmp *= pow(m-k,mod-2,mod)  
        tmp %= mod
    print(ans)
    return


if __name__ == '__main__':
    main()

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

Solution (Python):
N,M = list(map(int,input().split()))
p = 10**9+7

F = [1] * (5*10**5+1)
for i in range(1,5*10**5+1):
    F[i] = (F[i-1]*i)%p

MAXN = 5*(10**5)+10
MOD = p
f = [1]
for i in range(MAXN):
    f.append(f[-1] * (i+1) % MOD)
def nCr(n, r, mod=MOD):
    return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod

out = 0
for K in range(N+1):
    A = nCr(M,K,p)*F[K]
    B = nCr(M-K,N-K,p)*F[N-K]
    C = (-1)**K
    out = (out + nCr(N,K,p)*A*B*B*C)%p
print(out)

Solution (Python):
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)
c = comb(M, N, mod)
ans = ((fac[N] * c % mod) ** 2) % mod

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

Solution (Python):


import sys

class ENEQ:
    def solve(self, tc=0):
        from itertools import permutations
        MOD = 10 ** 9 + 7

        n, m = [int(_) for _ in input().split()]

        
        
        
        
        
        
        
        
        
        
        

        D = [0] * (n + 1)
        D[0] = 1
        D[1] = m - n
        for i in range(2, n + 1):
            D[i] = (m - n + i - 1) * D[i - 1] + (i - 1) * D[i - 2]
            D[i] %= MOD

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

        print(ans)

solver = ENEQ()
input = sys.stdin.readline

solver.solve()

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]


def cmb(n, r, mod=10**9+7):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

N = 10**6
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

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

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

ans=0


for i in range(n+1):
    onaji=g1[m]*g2[m-i]%mod
    tigau=(g1[m-i]*g2[m-n]%mod)**2%mod
    
    ans+=cmb(n,i)*((-1)**i)*onaji*tigau
    ans%=mod
print(ans)

Solution (Python):
n, m = map(int, input().split())
ans = 0
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 = 500001
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 )


for i in range(n+1):
    ans += pow(-1, i) * cmb(n, i, mod) * g1[m-i]*g2[m-n]
    ans %= mod

ans *= g1[m]*g2[m-n]
ans %= mod
print(ans)

Solution (Python):
import numpy as np

N = 10 ** 6
Nsq = 10 ** 3
mod = 10 ** 9 + 7

fac = np.arange(N, dtype=np.int64).reshape(Nsq, Nsq)
fac[0, 0] = 1
for i in range(1, Nsq):
    fac[:, i] *= fac[:, i - 1]
    fac[:, i] %= mod
for i in range(1, Nsq):
    fac[i] *= fac[i - 1, -1]
    fac[i] %= mod
fac = fac.ravel()

finv = np.arange(1, N + 1, dtype=np.int64)[::-1].reshape(Nsq, Nsq)
finv[0, 0] = pow(int(fac[N - 1]), mod - 2, mod)
for i in range(1, Nsq):
    finv[:, i] *= finv[:, i - 1]
    finv[:, i] %= mod
for i in range(1, Nsq):
    finv[i] *= finv[i - 1, -1]
    finv[i] %= mod
finv = finv.ravel()[::-1]


def nCr(a, b):
    comb = fac[a] * finv[b] % mod * finv[a - b] % mod
    return comb


def nPr(a, b):
    comb = fac[a] * finv[a - b] % mod
    return comb


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

res = 0
for i in range(n + 1):
    res += nCr(n, i) * (-1) ** i * nPr(m - i, n - i)
    res %= mod
print(res * nPr(m, n) % mod)

Solution (Python):
import sys

def S(): return sys.stdin.readline().rstrip()

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

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




ans = a**2 % mod
r = ans
for i in range(1,N+1):
    r *= (N-i+1)
    r %= mod
    r *= pow(i,mod-2,mod)
    r %= mod
    r *= pow(M-i+1,mod-2,mod)*(-1)
    r %= mod
    ans += r
    ans %= mod

print(ans)

Solution (Python):
import sys

def S(): return sys.stdin.readline().rstrip()

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

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




ans = a**2 % mod
r = ans
for i in range(1,N+1):
    r *= (N-i+1)*pow(i,mod-2,mod)*pow(M-i+1,mod-2,mod)*(-1)
    r %= mod
    ans += r
    ans %= mod

print(ans)

Solution (Python):
mod = 10 ** 9 + 7

SIZE = 5 * 10 ** 5 + 1
fact = [0] * SIZE
inv = [0] * SIZE
finv = [0] * SIZE
fact[0], fact[1] = 1, 1
inv[1] = 1
finv[0], finv[1] = 1, 1
for i in range(2, SIZE):
    fact[i] = fact[i - 1] * i % mod
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    finv[i] = finv[i - 1] * inv[i] % mod


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


def nPr(n, r):
    if n < 0 or r < 0 or n < r:
        return 0
    return fact[n] * finv[n - r] % mod


n, m = map(int, input().split())
ans = 0
for i in range(n+1):
    ans += (-1)**i * nCr(n, i) * nPr(m, i) * nPr(m-i, n-i) ** 2 % mod
    ans %= mod

print(ans)

Solution (Python):
import sys

def S(): return sys.stdin.readline().rstrip()

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

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




ans = a**2 % mod
r = ans
for i in range(1,N+1):
    r *= (N-i+1)*pow(i,-1,mod)*pow(M-i+1,-1,mod)*(-1)
    r %= mod
    ans += r
    ans %= mod

print(ans)

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

d = [0]*(M+1)
d[0] = 1
for i in range(1, M+1):
    d[i] = (d[i-1]*i)%P

ans = d[M]*pow(d[M-N], P-2, P)
ans **= 2
ans %= P
for i in range(1, N+1):
    temp = (d[N]*pow(d[N-i], P-2, P)*pow(d[i], P-2, P))%P
    temp *= d[M]
    temp %= P
    temp *= pow(d[M-i], P-2, P)
    temp %= P
    temp *= ((d[M-i]*pow(d[max(M-N, 1)], P-2, P))**2)%P
    ans += (temp%P)*(-1)**i
    ans %= P
print(ans%P)

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

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

def comb(n, k): return (fact[n] * revfact[n-k] * revfact[k]) % mod

def solve():
      Perm = [1] * (N + 1) 
      P = 1
      for i in reversed(range(N)): 
            Perm[i] = ((M - i) * Perm[i + 1]) % mod

      Ans = pow(Perm[i], 2, mod)

      for i in range(1, N + 1):
            P *= (M - i + 1)
            P %= mod
            Ans += pow(-1, i % 2) * (comb(N, i) * P * pow(Perm[i], 2, mod)) % mod
            Ans %= mod

      print(Ans)
      
      return 0

if __name__ == "__main__":
      solve()

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

MAX = 5 * 10 ** 5

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

inv = [1] * (MAX + 1)
for i in range(2, MAX + 1):
    inv[i] = inv[mod % i] * (mod - mod // i) % mod

fact_inv = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact_inv[i] = fact_inv[i-1] * inv[i] % mod


def comb(n, k):
    if n < k:
        return 0
    return fact[n] * fact_inv[n-k] * fact_inv[k] % mod


p1 = 1
p2 = 1

for i in range(m, m - n, -1):
    p2 *= i
    p2 %= mod

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

    p1 *= m - i
    p1 %= mod

    p2 *= inv[m - i]
    p2 %= mod

print(ans)

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

MAX = 5 * 10 ** 5

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

inv = [1] * (MAX + 1)
for i in range(2, MAX + 1):
    inv[i] = inv[mod % i] * (mod - mod // i) % mod

fact_inv = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact_inv[i] = fact_inv[i-1] * inv[i] % mod


def comb(n, k):
    if n < k:
        return 0
    return fact[n] * fact_inv[n-k] * fact_inv[k] % mod


p1 = 1
p2 = 1

for i in range(m, m - n, -1):
    p2 *= i
    p2 %= mod

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

    p1 *= m - i
    p1 %= mod

    p2 *= inv[m - i]
    p2 %= mod

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

U = 5*10**5
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD
 
def perm(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[n-k]
    z %= MOD
    return z

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z *= fact_inv[n-k]
    z %= MOD
    return z

n, m = map(int, input().split())
ans = 0
for i in range(n+1):
  temp = (-1)**i * comb(n, i)
  temp *= perm(m, i)
  temp %= MOD
  temp *= perm(m-i, n-i)**2
  temp %= MOD
  ans += temp
  ans %= MOD
print(ans)

Solution (Python):
mod = 10**9+7
M = 5*10**5

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

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

for n in range(N+1):
    ans += (-1)**n*fact[N]*factinv[n]*factinv[N-n]*fact[M]*factinv[M-n]*fact[M-n]*factinv[M-N]*fact[M-n]*factinv[M-N]%mod
    ans %= mod
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

U = 10**6
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD
 
def perm(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[n-k]
    z %= MOD
    return z

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z *= fact_inv[n-k]
    z %= MOD
    return z

n, m = map(int, input().split())
ans = 0
for i in range(n+1):
  temp = (-1)**i * comb(n, i)
  temp *= perm(m, i)
  temp %= MOD
  temp *= perm(m-i, n-i)**2
  temp %= MOD
  ans += temp
  ans %= MOD
print(ans)

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

p = 1
for i in range(n):
  p *= m-i
  p %= mod
dp = [0,1]
for i in range(n):
  tmp = dp[-2]*i + dp[-1]*(i+d)
  tmp %= mod
  dp.append(tmp)

p *= dp[-1]
p %= mod
print(p)

Solution (Python):
class Combination:
    """階乗とその逆元のテーブルをO(N)で事前作成し、組み合わせの計算をO(1)で行う"""
    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [0] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], MOD - 2, MOD)
        for i in reversed(range(n)):
            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD
        self.MOD = MOD

    def inverse(self, k):
        """kの逆元を求める O(1)"""
        return (self.inv_fact[k] * self.fact[k - 1]) % self.MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD

    def combination2(self, k, r):
        """kCrを求める O(r)
        kが大きいが、r <= nを満たしているときに使用
        """
        if k < r:
            return 0
        res = 1
        for l in range(r):
            res *= (k - l)
            res %= self.MOD
        return (res * self.inv_fact[r]) % self.MOD


n, m = map(int, input().split())
MOD = 10 ** 9 + 7
comb = Combination(10 ** 6, MOD)


dp = [0] * (n + 1)
sum_ = 0
for match_cnt in range(n + 1):
    tmp = comb.combination(n, match_cnt)
    tmp *= comb.permutation(m, match_cnt)
    tmp *= comb.permutation(m - match_cnt, n - match_cnt)
    tmp *= comb.permutation(m - match_cnt, n - match_cnt)
    dp[match_cnt] = tmp
    dp[match_cnt] %= MOD
ans = 0
for i in range(n + 1):
    ans += dp[i] * (-1) ** i
    ans %= MOD
print(ans)

Solution (Python):
def main():
    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 5*(10**5)+1):
        fact.append(fact[-1]*i % mod)

    def nPr(n, r, mod=10**9+7):
        return pow(fact[n-r], mod-2, mod)*fact[n] % mod
    n, m = map(int, input().split())
    if m == 1:
        print(0)
        return
    ans = nPr(m, n)
    if m-n == 1:
        a0 = 1
    else:
        a0 = 0
    a1 = 1
    for i in range((m-n-1), m-1):
        a1, a0 = ((i+1)*a1+(i-(m-n-1))*a0) % mod, a1
    print(a1*ans % mod)


main()

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

ans = M
for i in range(M-1, M-N, -1):
    ans = ans*i % mod



prev = 1
ansB = M-1


for i in range(1, N):
    tmp = (prev)*i % mod
    tmp2 = ansB - tmp % mod
    
    ansB = tmp * (M-i) % mod
    ansB += (tmp2)*(M-i-1) % mod
    
    
    ansB %= mod
    prev = tmp2
    



print((ans*ansB) % mod)

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

ans = M
for i in range(M-1, M-N, -1):
    ans = ans*i % mod



prev = 1
ansB = M-1


for i in range(1, N):
    tmp = (prev)*i % mod
    tmp2 = ansB - tmp % mod
    
    ansB = tmp * (M-i) % mod
    ansB += (tmp2)*(M-i-1) % mod
    
    
    ansB %= mod
    prev = tmp2
    



print((ans*ansB) % mod)

Solution (Python):

import sys
input = sys.stdin.readline
MOD = 10**9 + 7
MAX_N = 10**6


fac = [1] + [0] * MAX_N
for i in range(1, MAX_N+1):
    fac[i] = fac[i-1] * (i) % MOD

fac_inv = [1] + [0] * MAX_N




fac_inv[MAX_N] = pow(fac[MAX_N], MOD-2, MOD)
for i in range(MAX_N, 1, -1):
    fac_inv[i-1] = fac_inv[i] * i % MOD

def mod_nCr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD

def mod_nPr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    tmp = fac_inv[n-r] % MOD
    return tmp * fac[n] % MOD

n, m = map(int, input().split())
ans = 0
for i in range(n+1):
    ans += mod_nCr(n, i) * mod_nPr(m-i, n-i) * (-1)**i % MOD
ans *= mod_nPr(m, n)
print(ans % MOD)

Solution (Python):
import sys
input = sys.stdin.readline

















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


mod = 10**9+7
def cmb(n, r, mod=mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NN = 6*10**5 
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

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



ans = 0
for k in range(N+1):
    ans = (ans + (-1)**k * cmb(N, k)*g1[M-k]*g2[M-N] ) % mod
print(ans*g1[M]*g2[M-N]%mod)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

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

mod = 10 ** 9 + 7
MAX = max(M,N)+10
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX
def cominit():
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    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
def cmb(n,r):
    if n < 0 or r < 0 or r > n:return 0
    if r > n/2: r = n-r        
    return fac[n] * (finv[r] * finv[n-r] % mod) % mod
def permu(n,r):
    return fac[n] * finv[n-r]

cominit()

ans = permu(M, N)%mod
minus = 0
for i in range(1, N+1):
    minus += (-1)**((i-1)&1)*cmb(N,i)*permu(M-i, N-i)
    minus %= mod
ans += mod - minus
ans %= mod
ans *= permu(M,N)
ans %= mod
print(ans)

Solution (Python):
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
if N == 1:
  print( nA * dp[N] % mod_ )  
else:
  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_ )

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

g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
for i in range(2,5*10**5+1): 
    g1.append((g1[-1] * i) % MOD)
    inverse.append((-inverse[MOD % i] * (MOD // i)) % MOD)
    g2.append((g2[-1] * inverse[-1]) % MOD)

def comb(n, r, mod=MOD):
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n-r] % mod

def perm(n, r, mod=MOD):
    return  g1[n] * g2[n-r] % mod


base = ans = perm(M, N, MOD)

for n in range(1, N+1):
    temp = (comb(N, n) * perm(M-n, N-n)) % MOD
    if n%2:
        base -= temp
    else:
        base += temp

print((ans*base) % MOD)

Solution (Python):
from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

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


SIZE = 10 ** 6 + 100
g1, g2, inv = [1, 1], [1, 1], [0, 1]
for i in range(2, SIZE + 1):
    g1.append((g1[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    g2.append((g2[-1] * inv[-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 r < 0 or r > n:
        return 0
    return g1[n] * g2[n - r] % MOD

tmp = nPr(M, N)
for i in range(1, N + 1):
    if i % 2:
        tmp -= nCr(N, i) * nPr(M - i, N - i)
    else:
        tmp += nCr(N, i) * nPr(M - i, N - i)
print((nPr(M, N) * tmp) % MOD)

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    
    mod = 10**9+7
    N = 5*10**5
    g1 = [1, 1] 
    g2 = [1, 1] 
    inverse = [0, 1] 
    for i in range(2,N+1):
        g1.append((g1[-1]*i)%mod)
        inverse.append((-inverse[mod % i]*(mod//i))%mod)
        g2.append((g2[-1]*inverse[-1])%mod)
    n,m = map(int,ipt().split())
    ans = g1[m]*g2[(m-n)]%mod
    dp = [0,m-n,((m-n)*2+1+(m-n)*(m-n-1))%mod]
    for i in range(3,n+1):
        dp.append(((i-1)*dp[-2]%mod+(m-n+i-1)*dp[-1]%mod)%mod)
    print(dp[n]*ans%mod)


    return

if __name__ == '__main__':
    main()

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

MOD = 10**9+7
class mint:
    def __init__(self, x):
        self.x = x % MOD if isinstance(x, int) else int(x) % MOD
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    def __iadd__(self, other):
        self.x += other.x if isinstance(other, mint) else other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __isub__(self, other):
        self.x += MOD-other.x if isinstance(other, mint) else MOD-other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __imul__(self, other):
        self.x *= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __imod__(self, other):
        self.x %= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __mod__(self, other):
        return (
            mint(self.x % other.x) if isinstance(other, mint) else
            mint(self.x % other)
        )
    def __truediv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rmod__(self, other):
        return (
            mint(other.x % self.x) if isinstance(other, mint) else
            mint(other % self.x)
        )
    def __rtruediv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )
class Comb():
    
    def __init__(self, n):
        self.n = n
        fact = [0]*(n+1) 
        ifact = [0]*(n+1) 
        fact[0] = mint(1)
        for i in range(1, n+1):
            fact[i] = fact[i-1]*i
        ifact[-1] = pow(fact[-1], MOD-2)
        for i in range(n, 0, -1):
            ifact[i-1] = ifact[i]*i
        self.fact = fact
        self.ifact = ifact
    def calc(self, n, k):
        if k<0 or k>n:
            return 0
        return self.fact[n]*self.ifact[n-k]

cb= Comb(500005)

ans = cb.calc(m,n)

cnt = 1
for i in range(1,n+1):
    if cnt%2:
        pm = -1
    else:
        pm = 1
    cnt += 1
    minus = cb.calc(m-i,n-i)*cb.calc(n,i)*cb.ifact[i]
    ans += pm*minus

ans*= cb.calc(m,n)
print(ans)