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:
'''
Let g(x) = 序列內數字唯一，且最多 x 個位置不同。
Let f(x) = 序列內數字唯一，且給定 x 個位置時，使這些位置不同的方法數。

題目所求是 C(N, N) f(N)。

其中 g(x) 代表有至少 N - x 個位置是相同。可以分三個部份填數字，注意順序會影響，所以要乘上全排序：
(1) N - x 個位置（數字必需相同）：C(M, N - x) * (N - x)! = P(M, N - x)
(2) 序列 A 其餘位置（可以隨便填，但不能用到 (1) 的數字）：C(M - (N - x), x) * x! = P(M - (N - x), x)
(3) 序列 B 其餘位置（可以隨便填，但不能用到 (1) 的數字）：C(M - (N - x), x) * x! = P(M - (N - x), x)
g(x) = (1) * (2) * (3)

g(x) 是「選定 0 個位置，使這些位置不同的方法數」、「選定 1 個位置，使這些位置不同的方法數」、…、「選定 N 個位置，使這些位置不同的方法數」，即

g(x) = C(x, 0) f(0) + C(x, 1) f(1) + ... + C(x, x) f(x)
     = sum( C(x, i) * f(i) for i in [0, x] )
根據二項式反演，得到
f(x) = sum( (-1) ** (x - i) * C(x, i) * g(i) for i in [0, x] )
'''

class CombMod:
    def __init__(self, V, p):
        self.fact = [1] * V
        self.finv = [1] * V
        for i in range(1, V):
            self.fact[i] = self.fact[i - 1] * i % p
        self.finv[-1] = pow(self.fact[-1], p - 2, p)
        for i in range(V - 2, 0, -1):
            self.finv[i] = self.finv[i + 1] * (i + 1) % p
        self.p = p
        
    def fact(self, a):
        return self.fact[a]
    
    def finv(self, a):
        return self.finv[a]

    def comb(self, a, b):
        return self.fact[a] * self.finv[b] % self.p * self.finv[a - b] % self.p
        
    def perm(self, a, b):
        return self.fact[a] * self.finv[a - b] % self.p
    
    def hcomb(self, a, b):
        return self.comb(a + b - 1, b)


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

ans = 0
for i in range(0, N + 1):
    p1 = tool.perm(M, N - i)
    p2 = tool.perm(M - (N - i), i)
    g_i = p1 * p2 % mod * p2 % mod
    val = pow(-1, N - i, mod) * tool.comb(N, i) % mod * g_i % mod
    ans = (ans + val) % mod
print(ans)

Submission status: Accepted

Solution code:
# 二項係数のmod (大量のmod計算が必要なとき)
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

def per(n, r, mod):
    if (r < 0 or r > n):
        return 0

    return g1[n] * g2[n-r]  % mod

mod = 10 ** 9 + 7
N = 10 ** 6 # 出力の制限
g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

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

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

# 順列の総数
ans=per(m,n,mod)


cnt=0
for i in range(n+1):
    if i%2==0:
        cnt+=per(m-i,n-i,mod)*cmb(n,i,mod)
    else:
        cnt-=per(m-i,n-i,mod)*cmb(n,i,mod)

    cnt%=mod
print((ans*cnt)%mod)

Submission status: Accepted

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

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

def perm(n,r):
  global mod
  if r>n:
    return g1[n]
  if r<0:
    return 0
  return (g1[n]*g2[n-r])%mod

g1=[1,1]
g2=[1,1]
inv=[0,1]
for i in range(2,M+M+5):
  g1.append((g1[-1]*i)%mod)
  inv.append((-inv[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inv[-1])%mod)
P=0
for i in range(N+1):
  P+=pow(-1,i)*cmb(N,i)*perm(M,i)*perm(M-i,N-i)**2
print(P%mod)

Submission status: Accepted

Solution code:
class Modulo_Error(Exception):
    pass

class Modulo():
    def __init__(self,a,n):
        self.a=a%n
        self.n=n

    def __str__(self):
        return "{} (mod {})".format(self.a,self.n)

    #+,-
    def __pos__(self):
        return self

    def __neg__(self):
        return  Modulo(-self.a,self.n)

    #等号,不等号
    def __eq__(self,other):
        if isinstance(other,Modulo):
            return (self.a==other.a) and (self.n==other.n)
        elif isinstance(other,int):
            return (self-other).a==0

    def __neq__(self,other):
        return not(self==other)
    
    #加法
    def __add__(self,other):
        if isinstance(other,Modulo):
            if self.n!=other.n:
                raise Modulo_Error("異なる法同士の演算です.")
            return Modulo(self.a+other.a,self.n)
        elif isinstance(other,int):
            return Modulo(self.a+other,self.n)

    def __radd__(self,other):
        if isinstance(other,int):
            return Modulo(self.a+other,self.n)
        
    #減法
    def __sub__(self,other):
        return self+(-other)

    def __rsub__(self,other):
        if isinstance(other,int):
            return -self+other
        
    #乗法
    def __mul__(self,other):
        if isinstance(other,Modulo):
            if self.n!=other.n:
                raise Modulo_Error("異なる法同士の演算です.")
            return Modulo(self.a*other.a,self.n)
        elif isinstance(other,int):
            return Modulo(self.a*other,self.n)
        
    def __rmul__(self,other):
        if isinstance(other,int):
            return Modulo(self.a*other,self.n)
        
    #Modulo逆数
    def Modulo_Inverse(self):
        x0, y0, x1, y1 = 1, 0, 0, 1
        a,b=self.a,self.n
        while b != 0:
            q, a, b = a // b, b, a % b
            x0, x1 = x1, x0 - q * x1
            y0, y1 = y1, y0 - q * y1

        if a!=1:
            raise Modulo_Error("{}の逆数が存在しません".format(self))
        else:
            return Modulo(x0,self.n)
        
    #除法
    def __truediv__(self,other):
        return self*(other.Modulo_Inverse())
    
    def __rtruediv__(self,other):
        return other*(self.Modulo_Inverse())

    #累乗
    def __pow__(self,m):
        u=abs(m)

        r=Modulo(1,self.n)

        while u>0:
            if u%2==1:
                r*=self
            self*=self
            u=u>>1

        if m>=0:
            return r
        else:
            return r.Modulo_Inverse()

#階乗の剰余のリスト
def Factorial_Modulo_List(N,M,Inverse=False):
    X=[0]*(N+1)
    X[0]=Modulo(1,M)
    
    for i in range(1,N+1):
        X[i]=X[i-1]*i

    if Inverse:
        Y=[0]*(N+1)
        Y[-1]=1/X[-1]
        
        for j in range(N-1,-1,-1):
            Y[j]=Y[j+1]*(j+1)
        return X,Y
    else:
        return X
#---------------------------------------------------------------------
def nPr(n,r):
    return F[n]*G[n-r]

def nCr(n,r):
    return F[n]*G[n-r]*G[r]

A=10**9+7
N,M=map(int,input().split())
F,G=Factorial_Modulo_List(M,A,True)

Q=0
sgn=1
for k in range(N+1):
    Q+=sgn*nCr(N,k)*nPr(M,k)*nPr(M-k,N-k)**2
    sgn*=-1
print(Q.a)

Submission status: Accepted

Solution code:
n, m = map(int, input().split(' '))
mod = int(1e9 + 7)

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

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

s = 0
for k in range(n+1):
	n_choose_k = (l[n] * l2[k] * l2[n-k]) % mod
	m_perm_k = (l[m] * l2[m-k]) % mod
	mk_perm_nk = (l[m-k] * l2[m-n]) % mod
	s += ((-1) ** k * n_choose_k * m_perm_k * mk_perm_nk ** 2 ) % mod 

print(s % mod)

Submission status: Accepted

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    if sys.argv[-1] == 'ONLINE_JUDGE':
        import numba
        from numba.pycc import CC
        i8 = numba.int64
        cc = CC('my_module')
 
        def cc_export(f, signature):
            cc.export(f.__name__, signature)(f)
            return numba.njit(f)
 
            fact_table = cc_export(fact_table, (i8, i8))
            main = cc_export(main, (i8, i8, i8))
            cc.compile()

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

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

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

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

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
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)))


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

class Combination(object):
    def __init__(self, N, mod=MOD):
        fac, finv, inv = [0] * (N + 1), [0] * (N + 1), [0] * (N + 1)
        fac[:2] = 1, 1
        finv[:2] = 1, 1
        inv[1] = 1
        for i in range(2, N + 1):
            fac[i] = fac[i - 1] * i % mod
            inv[i] = -inv[mod % i] * (mod // i) % mod
            finv[i] = finv[i - 1] * inv[i] % mod
        self.N = N
        self.MOD = mod
        self.fac = fac
        self.finv = finv
        self.inv = inv

    def __call__(self, n, k):
        return self.C(n, k)

    def C(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        fac = self.fac
        finv = self.finv
        mod = self.MOD
        return fac[n] * (finv[k] * finv[n - k] % mod) % mod

    def P(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        return self.fac[n] * self.finv[n - k]


def main():
    N, M = MAP()
    ans = 0

    cmb = Combination(M)

    sign = +1
    for i in range(N+1):
        ans += sign * cmb.P(M-i, N-i) * cmb(N, i)
        ans %= MOD
        sign *= -1
    ans *= cmb.P(M, N)
    ans %= MOD
    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    n, m = map(int, input().split())

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

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

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

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

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

Submission status: Accepted

Solution code:
def examA():
    N = I()
    ans = N + N**2 + N**3
    print(ans)
    return

def examB():
    S = SI()
    T = SI()
    ans = 0
    for s,t in zip(S,T):
        if s!=t:
            ans += 1
    print(ans)
    return

def examC():
    N, M, K = LI()
    A = LI()
    B = LI()
    SA = 0
    b = 0
    SB = 0
    for i in range(M):
        if SB+B[i]>K:
            break
        SB += B[i]
        b += 1
    #print(b,SB)
    ans = 0
    ans = max(ans,b)
    for i in range(N):
        SA += A[i]
        if SA+SB>K:
            while(b>=0):
                if SA+SB<=K:
                    break
                SB -= B[b-1]
                b -= 1
        if b==-1:
            break
        #print(i,b,SA,SB)

        ans = max(ans,b+i+1)
    print(ans)
    return

def examD():
    def primes(n):
        is_prime = [True] * (n + 1)
        is_prime[0] = False
        is_prime[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if not is_prime[i]:
                continue
            for j in range(i * 2, n + 1, i):
                is_prime[j] = False
        return [i for i in range(n + 1) if is_prime[i]]
    N = I()
    P = primes(N)
    #print(P)
    D = [1]*(N+1)
    for p in P:
        for i in range(1,1+N//p):
            cnt = 1
            cur = i
            while(cur%p==0):
                cnt += 1
                cur //= p
            D[p*i] *= (1+cnt)

    ans = 0
    for i in range(1,N+1):
        ans += i*D[i]
    print(ans)
    return

def examE():
    class combination():
        # 素数のmod取るときのみ　速い
        def __init__(self, n, mod):
            self.n = n
            self.mod = mod
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

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

        def comb(self, n, r):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod
    N, M = LI()
    # 被りあり
    dp = [0] * (N + 1)
    dp[2] = 1
    for n in range(3, N + 1):
        dp[n] += (dp[n - 1] + dp[n - 2]) * (n - 1)
        dp[n] %= mod
    #print(dp)
    C = combination(M,mod)
    Acur = C.fac[M]
    Acur %= mod
    #print(Acur)
    for i in range(1,N+1):
        cur = C.comb(N,i)*C.fac[M-i]*C.inv[M-N]
        cur %= mod
        if i%2==1:
            Acur = Acur + mod - cur
        else:
            Acur = Acur + mod + cur
        Acur %= mod
        #print(Acur,cur)
    if N%2==1:
        Acur += 1
    ans = dp[N] * ((C.fac[M] * (C.inv[M-N])))
    ans %= mod
    print(ans)
    return

def examE2():
    class combination():
        # 素数のmod取るときのみ　速い
        def __init__(self, n, mod):
            self.n = n
            self.mod = mod
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

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

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

    N, M = LI()
    C = combination(M,mod)
    cnt = 0
    for i in range(N+1):
        cur = C.comb(N,i)*C.fac[M-i]*C.inv[M-N] % mod
        if i%2==1:
            cnt -= cur
            cnt += mod
            cnt %= mod
        else:
            cnt += cur
            cnt %= mod
    ans = cnt * (C.fac[M]*C.inv[M-N])
    ans %= mod
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE2()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

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

class Combination:
    def __init__(self, size):
        self.size = size + 2
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % mod
            self.inv[i] = -self.inv[mod % i] * (mod // i) % mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % mod

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

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

    def nhr(self, n, r):  # 重複組合せ: x_1 + ... + x_n = r
        return self.ncr(n + r - 1, n - 1)

comb = Combination(M + 100)

A = comb.npr(M, N) % mod

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

print(A * B % mod)

Submission status: Accepted

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return map(int, sys.stdin.readline().split())
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())


def FLIST(n):
    res = [1]
    for i in range(1, n+1):
        res.append(res[i-1]*i % DVSR)
    return res


N, M = LI()
FACT = FLIST(M)


def NCR(n, r):
    res = 1
    res *= FACT[n-r]
    res *= FACT[r]
    res %= DVSR
    res = INV(res)
    res *= FACT[n]
    res %= DVSR
    return res


def NPR(n, r):
    res = 1
    res *= FACT[n]
    res *= INV(FACT[n-r])
    res %= DVSR
    return res


ALL = NPR(M, N)
ALL %= DVSR
ALL *= ALL
ALL %= DVSR


PAT = 0
for i in reversed(range(1, N+1)):
    v = NCR(N, i)
    v *= NPR(M, i)
    v %= DVSR
    v *= NPR(M-i, N-i)
    v %= DVSR
    v *= NPR(M-i, N-i)
    v %= DVSR
    PAT = v - PAT
    PAT %= DVSR

print((ALL - PAT) % DVSR)

Submission status: Accepted

Solution code:
from functools import lru_cache

class Combination:
    def __init__(self, size):
        self.size = size + 2
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % MOD
            self.inv[i] = -self.inv[MOD % i] * (MOD // i) % MOD
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % MOD

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % MOD

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % MOD) % MOD

    def nhr(self, n, r):  # 重複組合せ: x_1 + ... + x_n = r
        return self.ncr(n + r - 1, n - 1)

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

ans = 0
for k in range(N + 1):
    ans += comb.ncr(N, k) * ((-1)**k) * comb.npr(M, k) * (comb.npr(M - k, N - k)**2)
    ans %= MOD
print(ans)

Submission status: Accepted

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

MOD = 10 ** 9 + 7

factorial = [1, 1]
inverse = [1, 1]
invere_base = [0, 1]
for i in range(2, N + M + 1):
    factorial.append((factorial[-1] * i) % MOD)
    invere_base.append((-invere_base[MOD % i] * (MOD // i)) % MOD)
    inverse.append((inverse[-1] * invere_base[-1]) % MOD)

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

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

mod = MOD
ans = 0

n = N
m = M

if N == M:
    for i in range(N+1):
        #print(cmb(n,i,mod),i)
        ans += nCr(n,i)*factorial[n]*factorial[n-i]*(-1)**(i)
        #print(ans)
        ans %= mod
        #print(ans)
    print(ans)
else:
    for i in range(N+1):
        ans += nCr(n,i)*nPr(m,n)*nPr(m-i,n-i)*(-1)**(i)
        ans %= mod
        #print(ans)
    print(ans)

Submission status: Accepted

Solution code:
class Comb():
    def __init__(self, N, mod=1):
        self.mod = mod
        fct = [1]
        invfct = [1]
        for i in range(1, N+1):
            fct.append(fct[i-1] * i % mod)
            invfct.append(pow(fct[i], mod-2, mod))
        self.fct = fct
        self.invfct = invfct
    
    def cmb(self, n, k):
        """ Calculate nCk = n! / (k! * (n-k)!) mod self.mod """
        return self.fct[n] * self.invfct[k] * self.invfct[n-k]

    def pam(self, n, k):
        """ Calculate nPk = n! / (n-k)! mod self.mod """
        return self.fct[n] * self.invfct[n-k]
N, M = map(int, input().split())
mod = 10**9 + 7
comb = Comb(N+M, mod)
ans = 0
for k in range(N+1):
    ans += pow(-1, k) * comb.cmb(N, k) * comb.pam(M, k) * pow(comb.pam(M-k, N- k), 2)
    ans %= mod
print(ans)

Submission status: Accepted

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

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

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

fact = [0] * 1100000
invfact = [0] * 1100000

fact[0] = 1

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

invfact[-1] = pow(fact[-1], MOD-2, MOD)

for i in range(1100000-1, 0, -1):
  invfact[i-1] = invfact[i] * i % MOD

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
# Settings
mod = 10**9+7


# Preparation
def inv(a, mod):
    r = [1, 0, a]
    w = [0, 1, mod]
    while w[2] != 1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0], r[1]-q*w[1], r[2]-q*w[2]]
        r = w
        w = r_new
    x, y = w[0], w[1]    # a*x+y*mod = 1
    return (mod+x % mod) % mod


max_num = 5*10**5+2  # 10**6 にしたほうがよい?
fact = [0 for _ in range(max_num)]
ifact = [0 for _ in range(max_num)]

fact[0] = fact[1] = 1
ifact[0] = ifact[1] = 1

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

ifact[max_num-1] = inv(fact[max_num-1], mod)

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


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


# Code
def solve():
    tmp = 0
    for i in range(1, n+1):
        tmp2 = comb(n, i) * fact[m-i] * ifact[m-n]
        tmp2 %= mod
        tmp += (-1)**(i-1)*tmp2

    tmp = fact[m]*ifact[m-n] - tmp
    tmp %= mod

    ans = tmp*fact[m]*ifact[m-n]
    ans %= mod

    return ans


if __name__ == "__main__":
    n, m = map(int, input().split())
    print(solve())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#nCをp(=10**9+7)で割ったときのあまり(モジュラ逆数)
def cmb(n,r,p):
  if r<0 or n<r:
    return 0
  r=min(r,n-r)
  return facto[n]*factoinv[r]*factoinv[n-r]%p
p=10**9+7
n,m=map(int,input().split())
#0,1の時の値をいれたn!のリスト(modp)
facto=[1,1]
#0,1の時の値をいれたn!の逆元のリスト(modp)
factoinv=[1,1]
#0,1の場合を入れたn!の逆元も求めるために使うnの逆元のリスト(modp)
inv=[0,1]
#2からスタート
for i in range(2,m+1):
  facto.append((facto[-1]*i)%p)
  inv.append((-inv[p%i]*(p//i))%p)
  factoinv.append((factoinv[-1]*inv[-1])%p)
if n==m:
  kosuub=0
  for i in range(n+1):
    kosuub+=(facto[(n-i)]*cmb(n,i,p)*((-1)**i))%p
  kosuu=(kosuub*facto[(n)])%p
  print(kosuu)
else:
  kosuub=0
  for i in range(n+1):
    kosuub+=(cmb((m-i),(n-i),p)*facto[(n-i)]*cmb(n,i,p)*((-1)**i))%p
  kosuu=(kosuub*cmb(m,n,p)*facto[n])%p
  print(kosuu)

Submission status: Accepted

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

MAX = 5*10**5+100
MOD = 10**9+7
fact = [0]*MAX #fact[i]: i!
inv = [0]*MAX #inv[i]: iの逆元
finv = [0]*MAX #finv[i]: i!の逆元
fact[0] = 1
fact[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
    
for i in range(2, MAX):
    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 C(n, r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fact[n]*(finv[r]*finv[n-r]%MOD)%MOD

N, M = map(int, input().split())
ans = (C(M, N)*fact[N])**2%MOD

for i in range(1, N+1):
    if i%2==0:
        ans += C(N, i)*C(M, i)*fact[i]*(C(M-i, N-i)*fact[N-i])**2
    else:
        ans -= C(N, i)*C(M, i)*fact[i]*(C(M-i, N-i)*fact[N-i])**2
    
    ans %= MOD

print(ans)

Submission status: Accepted

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

factorial = [1]
inverse = [1]
for i in range(1, m+1):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod - 2, mod))
def comb(n, r, mod):
    if n < r or r < 0: return 0
    elif r == 0: return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod
def perm(n, r, mod):
    if n < r or r < 0: return 0
    elif r == 0: return 1
    return factorial[n] * inverse[n - r] % mod

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,M = map(int,input().split())
fac = [1, 1]
inv = [0, 1]
finv = [1, 1]
MOD = 10**9+7
fac = [1, 1]
inv = [0, 1]
finv = [1, 1]
for i in range(2, M+1):
    fac.append(fac[-1] * i % MOD)
    inv.append(MOD - inv[MOD%i] * (MOD//i) % MOD)
    finv.append(finv[-1] * inv[-1] % MOD) 
def comb_mod(n, r, m):  #nCr mod m
    if (n<0 or r<0 or n<r): return 0
    r = min(r, n-r)
    return fac[n] * finv[n-r] * finv[r] % m

def chofuku(n,r): # nHr mod MOD の計算
    return comb_mod(n+r-1,r)
 
def nPr(n,r,m): #nPr mod m の計算
    return fac[n]*finv[n-r]%m
ans = 0
for i in range(1,N+1):
    if i % 2 == 1:
        flag = 1
    else:
        flag = -1
    s = flag*comb_mod(N,i,MOD)*nPr(M-i,N-i,MOD)
    ans += s
    if ans > MOD:
        ans %= MOD
ans1 = 1
for i in range(N):
    ans1 *= (M-i)
    ans1 %= MOD
ans2 = (ans1*ans1)%MOD
ans3 = (ans*nPr(M,N,MOD)) %MOD
print((ans2-ans3)%MOD)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
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 = 5*10**5 #Nの最大値
g1 = [0]*(N+1) #元テーブル
g1[0] = g1[1] = 1
g2 = [0]*(N+1) #逆元テーブル
g2[0] = g2[1] = 1
inverse = [0]*(N+1) #逆元テーブル計算用テーブル
inverse[0],inverse[1] = 0,1
for i in range(2,N+1):
    g1[i] = (g1[i-1] * i) % mod
    inverse[i] = (-inverse[mod % i] * (mod//i)) % mod
    g2[i] = (g2[i-1] * inverse[i]) % mod

N, M = map(int, input().split())
ans = 0
for i in range(N+1):
    ans += cmb(N,i,mod)*((-1)**i)*g1[M]*g2[M-i]*((g1[M-i]*g2[M-N])**2)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
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 = 5*10**5 #Nの最大値
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):
    ans += cmb(N,i,mod)*((-1)**i)*g1[M]*g2[M-i]*((g1[M-i]*g2[M-N])**2)
    ans %= mod
print(ans)