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


import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,m = map(int,readline().split())
"""
漸化式は f(m,n) = (m-1)f(m-1,n-1) + (n-1)f(m-2,n-2)
初期条件 f(m-n,0)=1, f(m-n+1,1)=m-n
"""
MOD = 10**9+7
res = [0]*(n+1)
res[0] = 1
res[1] = m-n
for i in range(2,n+1):
    res[i] = (m-n+i-1)*res[i-1] + (i-1)*res[i-2]
    res[i] %= MOD


ans = res[n] 
for i in range(m,m-n,-1):
    ans *= i
    ans %= MOD

print(ans)

Solution (Python):

from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    N, M = map(int, input().split())
    p = 10**9 + 7
    
    a = [None] * (M+1)
    inva = [None] * (M+1)
    a[0] = 1
    for i in range(1, M+1):
        a[i] = i * a[i-1] % p
    inva[M] = pow(a[M],p-2,p)
    for i in range(M):
        inva[M-i-1] = inva[M-i] * (M-i) % p

    ans = 0
    for k in range(N+1):
        
        tmp = (a[N] * inva[N-k] % p) * inva[k] % p
        
        if k % 2 == 1:
            tmp = -tmp % p
        
        tmp = (tmp * a[M] % p) * inva[M-k] % p

        
        tmp *= pow(a[M-k] * inva[M-N] % p, 2, p)
        tmp %= p
        ans += tmp
        ans %= p
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
mod = 10**9 + 7
n, m = map(int, input().split())

def make_tables(n, mod = 10 ** 9 + 7):
    fac = [1, 1] 
    finv = [1, 1] 
    inv = [0, 1] 

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

def nCk(n, k, mod = 10 ** 9 + 7):
    k = min(k, n-k)
    return fac[n] * finv[k] * finv[n-k] % mod


fac, finv = make_tables(m)

a_sum = fac[m] * finv[m - n] % mod

ng = 0
kaburi = [0]
for i in range(1, n + 1):
    c = (nCk(n, i) * fac[(m - i)] * finv[m - n] % mod)
    kaburi.append(c)

for i in range(1, n + 1):
    if i % 2:
        ng += kaburi[i]
    else:
        ng -= kaburi[i]

print((a_sum * (a_sum - ng)) % mod)

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

MOD = 10**9 + 7
MAX = m + 1
fact = [1] * (MAX + 1)  
finv = [1] * (MAX + 1)  
iinv = [1] * (MAX + 1)  
for i in range(2, MAX + 1):
    fact[i] = fact[i - 1] * i % MOD
    iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * iinv[i] % MOD


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


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


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

ans *= perm(m, n)
ans %= MOD

print(ans)

Solution (Python):

class Combination:
    def __init__(self, n, mod):
        fact = [0]*(n+1)
        ifact = [0]*(n+1)
        fact[0] = 1
        for i in range(1, n+1):
            fact[i] = (fact[i-1]*i) % mod
        
        ifact[n] = pow(fact[n], mod-2, mod)
        for i in range(n, 0, -1):
            ifact[i-1] = (ifact[i]*i) % mod

        self.n = n
        self.mod = mod
        self.fact = fact
        self.ifact = ifact

    def c(self, n, r):
        if r < 0 or r > n:
            return 0
        ret = (self.fact[n]*self.ifact[r]) % self.mod
        return (ret*self.ifact[n-r]) % self.mod

    def p(self, n, r):
        if n < r:
            return 0
        return self.fact[n]*self.ifact[n-r] % self.mod


MOD = 10**9+7
N, M = map(int, input().split())
c = Combination(M, MOD)
ans = 0
for i in range(N+1):
    a = (-1)**i * c.c(N, i)*c.p(M, i)*(c.p(M-i, N-i)**2) % MOD
    ans = (ans+a) % MOD
print(ans)

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

mod = 10**9 + 7

class Combination:
    def __init__(self, n):
        self.facts = [1 for i in range(n+1)]
        self.invs = [1 for i in range(n+1)]

        for i in range(1, n+1):
            self.facts[i] = self.facts[i-1] * i % mod
        self.invs[n] = pow(self.facts[n], mod-2, mod)
        for i in range(1, n+1):
            self.invs[n-i] = self.invs[n-i+1] * (n-i+1) % mod

    def ncr(self, n, r):
        if n < r:
            return 0
        if n < 0 or r < 0:
            return 0
        else:
            return self.facts[n] * self.invs[r] * self.invs[n-r] % mod

    def npr(self, n, r):
        if n < r:
            return 0
        if n < 0 or r < 0:
            return 0
        return self.facts[n] * self.invs[n-r] % mod

ans = 0
comb = Combination(M)
for i in range(N+1):
    ans = (ans + (-1) ** i * comb.npr(M-i, N-i) * comb.ncr(N, i)) % mod

ans = ans * comb.npr(M, N) % mod
print(ans)

Solution (Python):
def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

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

    return modFacts, invs
        

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

ans = 0
for i in range(N + 1):
    cnt = (modFacts[N] * invs[i] * invs[N - i]) % MOD
    cnt *= (modFacts[M] * invs[M - i]) % MOD
    cnt %= MOD
    cnt *= pow(modFacts[M - i] * invs[(M - i) - (N - i)], 2, MOD)
    cnt %= MOD
    ans += pow(-1, i) * cnt
    ans %= MOD

print(ans)

Solution (Python):
def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

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

    return modFacts, invs
        

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

ans = 0
for i in range(N + 1):
    cnt = (modFacts[N] * invs[i] * invs[N - i]) % MOD
    cnt *= (modFacts[M] * invs[M - i]) % MOD
    cnt %= MOD
    cnt *= pow(modFacts[M - i] * invs[(M - i) - (N - i)], 2, MOD)
    cnt %= MOD
    ans += pow(-1, i) * cnt
    ans %= MOD

print(ans)

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


class CombMod:

    def __init__(self, N, MOD=10**9 + 7):

        N = N + 1
        inv = [0] * N
        fact = [0] * N
        fact_inv = [0] * N

        inv[0] = 0
        inv[1] = 1
        for n in range(2, N):
            q, r = divmod(MOD, n)
            inv[n] = inv[r] * (-q) % MOD

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

        fact_inv[0] = 1
        for n in range(1, N):
            fact_inv[n] = fact_inv[n - 1] * inv[n] % MOD

        self.fact = fact
        self.fact_inv = fact_inv
        self.inv = inv

    def comb(self, n, r, mod=10**9 + 7):
        return self.fact[n] * self.fact_inv[r] % mod * self.fact_inv[n - r] % mod

    def perm(self, n, r, mod=10**9 + 7):
        return self.fact[n] * self.fact_inv[n - r] % mod


def main():

    N, M = in_nn()
    mod = 10**9 + 7
    c = CombMod(M)

    ans = c.perm(M, N)
    for k in range(1, N + 1):
        ans -= (-1)**(k - 1 % 2) * c.comb(N, k) * c.perm(M - k, N - k)
        ans %= mod

    ans *= c.perm(M, N)
    ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

lim = M+10  
fact = [1] * (lim+1)
fact_inv = [1] * (lim+1)
for n in range(1, lim+1):
    fact[n] = (fact[n-1] * n) % mod
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
    fact_inv[n-1] = (n * fact_inv[n]) % mod
def C(n, r):
    return (((fact[n] * fact_inv[r]) % mod) * fact_inv[n-r]) % mod

def P(n, r):
    return fact[n]*fact_inv[n-r]%mod

ans = 0
for k in range(N+1):
    now = C(N, k)
    now *= P(M-k, N-k)
    if k%2 == 1:
        now = -now
    ans += now
    ans %= mod
ans *= P(M, N)
ans %= mod
print(ans)

Solution (Python):


import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union






























def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    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 = [1] * (size + 1)
        for i in range(1, size + 1):
            fact_mod[i] = (fact_mod[i - 1] * i) % mod
        return fact_mod


    def make_inv_factorial_table(size: int, mod: int) -> List[int]:
        inv_fact_mod = [1] * (size + 1)
        n_fact = 1
        for i in range(2, size+1):
            n_fact = (n_fact * i) % mod
        inv_fact_mod[size] = pow(n_fact, mod-2, mod)    
        for i in range(size-1, -1, -1):
            inv_fact_mod[i] = (inv_fact_mod[i+1] * (i+1)) % mod    
        return inv_fact_mod    


    def combination(n: int, r: int, mod: int, fact_table: List[int], inv_fact_table: List[int]=[]) -> int:
        numerator = fact_table[n]
        if not inv_fact_table:
            
            denominator = pow((fact_table[n-r] * fact_table[r]) % mod, mod-2, mod)
        else:
            denominator = (inv_fact_table[n-r] * inv_fact_table[r]) % mod
            assert (fact_table[n-r] * inv_fact_table[n-r]) % mod == 1
            assert (fact_table[n-r] * fact_table[r] * inv_fact_table[n-r] * inv_fact_table[r]) % mod == 1
            assert pow((fact_table[n-r] * fact_table[r]) % mod, mod-2, mod) == denominator
        return (numerator * denominator) % mod



    n, m = mi()
    f = make_factorial_table(10 ** 6, mod)
    inv = make_inv_factorial_table(10 ** 6, mod)

    
    ans = 0
    for k in range(n + 1):
        if k % 2 == 0:
            cnt = 1
        else:
            cnt = -1
        cnt = (cnt * combination(n, k, mod, f, inv)) % mod
        cnt = (cnt * (combination(m, k, mod, f, inv) * f[k]) % mod) % mod
        cnt = (cnt * (combination(m-k, n-k, mod, f, inv) * f[n-k] % mod) ** 2 % mod) % mod
        ans = (ans + cnt) % mod
    print(ans)



if __name__ == "__main__":
    main()

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def comb(a,b):
        return f[a]*inv[b]*inv[a-b]%mod
    n,m = LI()
    N = n+m
    f = [1]*(N+1)
    for i in range(1,N+1):
        f[i] = f[i-1]*i%mod
    inv = [None]*(N+1)
    inv[N] = pow(f[N],mod-2,mod)
    for i in range(N)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    ans = comb(m,n)*f[n]
    for i in range(1,n+1):
        if i&1:
            ans -= comb(n,i)*comb(m-i,n-i)*f[n-i]%mod
        else:
            ans += comb(n,i)*comb(m-i,n-i)*f[n-i]%mod
        ans %= mod
    print(ans*comb(m,n)*f[n]%mod)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
class Combination():
    def __init__(self, n, mod):
        self.n = n
        self.mod = mod
        self.fact = self.make_fact(n)
        self.fact_inv = self.make_fact_inv(n)
    def make_fact(self, n):
        res = [1]*(n+1)
        for i in range(1, n+1):
            res[i] = res[i-1]*i%self.mod
        return res
    def make_fact_inv(self, n):
        fact_inv = [1]*(n+1)
        fact_inv[n] = pow(self.fact[n], self.mod-2, self.mod)
        for i in range(n, 0, -1):
            fact_inv[i-1] = fact_inv[i]*i%self.mod
        return fact_inv
    def c(self, m, k):
        return self.fact[m]*self.fact_inv[k]*self.fact_inv[m-k]%self.mod
    def p(self,m,k):
        return self.fact[m]*self.fact_inv[m-k] %self.mod
mod = 10**9+7

n,m=map(int,input().split())
com = Combination(m,mod)

ans=0
for i in range(n+1):
    ans += com.c(n,i) * (-1)**i * com.p(m,i) * (com.p(m-i,n-i))**2
    ans %= mod
    
print(ans)

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

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 comb(n,k):
    if k<0 or k>n:
        return 0
    x=fact[n]
    x*=fact_inv[k]
    x%=mod
    x*=fact_inv[n-k]
    x%=mod
    return x
def div(a,b):
    return (a*pow(b,mod-2,mod))%mod

def p(n,k):
    return div(fact[n],fact[n-k])
ans=0
for i in range(n+1):
    t=(comb(n,i)*p(m-i,n-i))%mod
    if i%2:ans=(ans-t)%mod
    else:ans=(ans+t)%mod
ans=(ans*p(m,n))%mod
print(ans)

Solution (Python):
def ext_euc(a, b):
    if b == 0:
        return 1, 0, a
    y, x, v = ext_euc(b, a % b)
    y -= (a // b) * x
    return x, y, v


def mod_inv(a, mod):
    ret, _, _ = ext_euc(a, mod)
    return ret % mod


def main():
    MOD = 10 ** 9 + 7
    N, M = list(map(int, input().split(' ')))
    comb = [1 for _ in range(N + 1)]  
    perm_1 = [1 for _ in range(N + 1)]  
    perm_2 = [1 for _ in range(N + 1)]  
    for k in range(1, N + 1):
        c = comb[k - 1] * (N - k + 1) * mod_inv(k, MOD)
        c %= MOD
        comb[k] = c
        p = perm_1[k - 1] * (M - k + 1)
        p %= MOD
        perm_1[k] = p
        p = perm_2[k - 1] * (M - N + k)
        p %= MOD
        perm_2[k] = p
    perm_2.reverse()
    ans = 0
    for k in range(N + 1):
        v = (-1) ** (k % 2)
        v *= comb[k]
        v %= MOD
        v *= perm_1[k]
        v %= MOD
        v *= perm_2[k]
        v %= MOD
        v *= perm_2[k]
        v %= MOD
        ans += v
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
mod=10**9+7
fact=[1]
for i in range(1,5*10**5+1):
  fact.append((fact[-1]*i)%mod)
revfact=[1]
for i in range(1,5*10**5+1):
  revfact.append(pow(fact[i],mod-2,mod))
n,m=map(int,input().split())
patternA=(fact[m]*revfact[n]*revfact[m-n]*fact[n])%mod
patternB=0
for i in range(n+1):
  tmp=(fact[n]*revfact[i]*revfact[n-i])*(fact[m-i]*revfact[n-i]*revfact[m-n])*fact[n-i]
  if i%2==0:
    patternB+=tmp
    patternB%=mod
  else:
    patternB-=tmp
    patternB%=mod
print((patternA*patternB)%mod)

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

def calc():
  mod=10**9+7
  fact=[1]
  for i in range(1,5*10**5+1):
    fact.append((fact[-1]*i)%mod)
  revfact=[1]
  for i in range(1,5*10**5+1):
    revfact.append(pow(fact[i],mod-2,mod))
  n,m=map(int,input().split())
  patternA=(fact[m]*revfact[n]*revfact[m-n]*fact[n])%mod
  patternB=0
  for i in range(n+1):
    tmp=(fact[n]*revfact[i]*revfact[n-i])*(fact[m-i]*revfact[m-n])
    if i%2==0:
      patternB+=tmp
    else:
      patternB-=tmp
      patternB%=mod
  print((patternA*patternB)%mod)
calc()

Solution (Python):
mod = 10**9+7
n,m = map(int,input().split())
fac = [1]*(m+1)
for i in range(1,m):
    fac[i+1] = fac[i] * (i+1) % mod
def inv(x):
    return pow(x,mod-2,mod)
def cmb(n,k,mod):
    return fac[n]*inv(fac[k])*inv(fac[n-k])
def per(n,k,mod):
    return fac[n]*inv(fac[n-k])
ans = 0
for k in range(n+1):
    ans += cmb(n,k,mod)*(-1)**k*per(m,k,mod)*per(m-k,n-k,mod)**2
    ans %= mod
print(ans)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


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


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 factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




N,M = IL()

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

Solution (Python):

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

mod = 10 ** 9 + 7
N = m + 5
bikkuri = [1 for i in range(N)]
for i in range(1, N):
    bikkuri[i] = (i * bikkuri[i - 1]) % mod

gyaku = [1 for i in range(N)]
gyaku[N - 1] = pow(bikkuri[N - 1], mod - 2, mod)
for i in range(N - 1, 0, -1):
    gyaku[i - 1] = (gyaku[i] * i) % mod


def perm(n, r):
    if r < 0:
        return 0
    if n == 0:
        return 1
    return (bikkuri[n] * gyaku[n - r]) % mod


def comb(n, r):
    if r < 0 or n - r < 0:
        return 0
    return (bikkuri[n] * gyaku[r] * gyaku[n - r]) % mod


ans = 0

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

print(ans % mod)

Solution (Python):
class Mod:
    def __init__(self, mod, n_max):
        """
        イニシャライザ
        予め 1~nの階乗と階乗の逆元を計算しておく
        :param mod: 法
        :param n_max: nの最大値(100,000で約1秒)
        """
        self.mod = mod
        self.n_max = n_max
        self.facts = [1, 1]
        self.inverses = [None, 1]
        self.fact_inverses = [1, 1]

        for i in range(2, self.n_max + 1):
            self.facts.append(self.facts[i - 1] * i % self.mod)
            
            self.inverses.append(
                self.mod - self.inverses[self.mod % i] *
                (self.mod // i) % self.mod
            )
            self.fact_inverses.append(
                self.fact_inverses[i - 1] * self.inverses[i] % self.mod
            )

    def combination(self, n, k):
        if k > n:
            raise ValueError
        elif k == n:
            return 1
        elif k == 0:
            return 1

        denominator = self.fact_inverses[k] * self.fact_inverses[n - k] % self.mod
        return self.facts[n] * denominator % self.mod

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


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

m = Mod(MOD, M)
mPn = m.permutation(M, N)

b = mPn
x = mPn

for k in range(1, N + 1):
    dup = m.permutation(M - k, N - k) * m.combination(N, k) % MOD
    if k % 2 == 1:
        b -= dup
    else:
        b += dup
    b %= MOD

print(mPn * b % MOD)

Solution (Python):
def main():

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

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

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

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

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

    if M < N: return 0

    ans = 0
    sgn = 1
    for i in range(N+1):
        v = sgn * combi(N, i) * p(M, i)
        v %= mod
        v *= p(M-i, N-i) * p(M-i, N-i)
        v %= mod
        ans += v
        ans %= mod
        sgn *= -1
    return ans



if __name__ == '__main__':
    print(main())

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):
mod = 10**9 + 7
P = 500009
Nr = [1 for _ in range(P + 1)]

for i in range(2, P +1):
    Nr[i] = (Nr[i-1] * i)%mod 

Dr = [1 for _ in range(P +1)]
Dr[P]  = pow(Nr[P] , mod - 2 , mod) 

for i in range(P, 0, -1):
    Dr[i-1] = (Dr[i]*i)%mod 
    
def ncr(n,r):
    if n  < r:
        return 0 
    else:
        return ((Nr[n] * Dr[r])%mod * Dr[n-r])%mod
        
def npr(n,r):
    if n<r:
        return 0 
    else:
        return (Nr[n] * Dr[n-r])%mod
        
n,m = map(int, input().split())       
ans = (npr(m,n)**2)%mod 

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

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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


N = m+n

g1 = [None] * (N+1) 
g2 = [None] * (N+1) 
inverse = [None] * (N+1) 
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

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

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


val = g1[n]*cmb(m,n,M)
val2 = 0
for i in range(1,n+1):
    val2 += cmb(n, i, M) * (g1[n-i]*cmb(m-i,n-i,M)) * pow(-1, i+1)
    val2 %= M
val2 = g1[n]*cmb(m,n,M) - val2
ans = (val*val2)%M
print(ans)

Solution (Python):
def cmb(n, r, p):
  if (r < 0) or (n < r):
    return 0
  r = min(r, n - r)
  return fac[n] * finv[r] * finv[n-r] % p

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

N = 5*pow(10,5)+100
MOD = pow(10,9)+7

fac = [-1]*(N+1); fac[0] = 1; fac[1] = 1 
finv = [-1]*(N+1); finv[0] = 1; finv[1] = 1 
inv = [-1]*(N+1); inv[0] = 0; inv[1] = 1 
for i in range(2,N+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

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

All = perm(m,n,MOD)**2
ans = All
for k in range(1,m+1):
  temp = cmb(n,k,MOD)*pow(-1,k-1)*perm(m,k,MOD)*(perm(m-k,n-k,MOD)**2)
  
  ans = (ans-temp)%MOD
print(ans)

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


class CombMod:

    def __init__(self, N, MOD=10**9 + 7):

        N = N + 1
        inv = [0] * N
        fact = [0] * N
        fact_inv = [0] * N

        inv[0] = 0
        inv[1] = 1
        for n in range(2, N):
            q, r = divmod(MOD, n)
            inv[n] = inv[r] * (-q) % MOD

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

        fact_inv[0] = 1
        for n in range(1, N):
            fact_inv[n] = fact_inv[n - 1] * inv[n] % MOD

        self.fact = fact
        self.fact_inv = fact_inv
        self.inv = inv

    def comb(self, n, r, mod=10**9 + 7):
        return self.fact[n] * self.fact_inv[r] % mod * self.fact_inv[n - r] % mod

    def perm(self, n, r, mod=10**9 + 7):
        return self.fact[n] * self.fact_inv[n - r] % mod


def main():

    N, M = in_nn()
    mod = 10**9 + 7
    c = CombMod(M)

    ans = 0
    for i in range(N + 1):
        t = c.comb(N, i)

        t *= (-1)**(i % 2)
        t %= mod

        t *= c.perm(M, i)
        t %= mod

        t *= c.perm(M - i, N - i)
        t %= mod

        t *= c.perm(M - i, N - i)
        t %= mod

        ans += t
        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    mod=1000000007
    inv=lambda x: pow(x,mod-2,mod)
    n,m=map(int,input().split())
    
    Fact=[1]
    for i in range(1,m+1):
        Fact.append(Fact[i-1]*i%mod)
    Finv=[0]*(m+1)
    Finv[-1]=inv(Fact[-1])
    for i in range(m-1,-1,-1):
        Finv[i]=Finv[i+1]*(i+1)%mod
    def comb(n,r):
        if n<r:
            return 0
        return Fact[n]*Finv[r]*Finv[n-r]%mod
    def perm(n,r):
        if n<r:
            return 0
        return Fact[n]*Finv[n-r]%mod
    
    ans=0
    p=1
    for i in range(n+1):
        ans+=comb(n,i)*perm(m,i)*perm(m-i,n-i)**2*p
        ans%=mod
        p*=-1
    print(ans)
    
if __name__=='__main__':
    main()

Solution (Python):
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


class CombMod:

    def __init__(self, N, MOD=10**9 + 7):

        N = N + 1
        inv = [0] * N
        fact = [0] * N
        fact_inv = [0] * N

        inv[0] = 0
        inv[1] = 1
        for n in range(2, N):
            q, r = divmod(MOD, n)
            inv[n] = inv[r] * (-q) % MOD

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

        fact_inv[0] = 1
        for n in range(1, N):
            fact_inv[n] = fact_inv[n - 1] * inv[n] % MOD

        self.fact = fact
        self.fact_inv = fact_inv
        self.inv = inv

    def comb(self, n, r, mod=10**9 + 7):
        return self.fact[n] * self.fact_inv[r] % mod * self.fact_inv[n - r] % mod

    def perm(self, n, r, mod=10**9 + 7):
        return self.fact[n] * self.fact_inv[n - r] % mod


def main():

    N, M = in_nn()
    mod = 10**9 + 7
    c = CombMod(M)

    ans = 0
    for i in range(N + 1):
        t = c.comb(N, i)

        t *= (-1)**(i % 2)
        t %= mod

        t *= c.perm(M, i)
        t %= mod

        t *= c.perm(M - i, N - i)
        t %= mod

        t *= c.perm(M - i, N - i)
        t %= mod

        ans += t
        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
import math
import bisect
from collections import deque
def input():
    return sys.stdin.readline()[:-1]

n,m = map(int,input().split())
mod = 10**9+7
ans =0
mpk = [0 for i in range(n+1)]
mpk[0] = 1
for i in range(1,n+1):
    mpk[i] = mpk[i-1]*(m+1-i)
    mpk[i] %= mod

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

lis = [1 for i in range(n+1)]
lis_r = [1 for i in range(n+1)]
for i in range(1,n+1):
    lis[i] = lis[i-1]*i
    lis[i] %= mod
    lis_r[i] = lis_r[i-1]*pow(i,mod-2,mod)
    lis_r[i] %= mod

for k in range(n+1):
    ans += (-1)**k*lis[n]*lis_r[n-k]*lis_r[k]*mpk[k]*(mkpnk[n-k])**2
    ans %= mod
print(ans)