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:
class Combination:                                      # 計算量は O(n_max + log(mod))
    def __init__(self, n_max, MOD=10 ** 9 + 7):
        self.mod = MOD
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):                     # 階乗(= n_max !)の逆元を生成
            f = f * i % MOD                             # 動的計画法による階乗の高速計算
            fac.append(f)                               # fac は階乗のリスト
        f = pow(f, MOD - 2, MOD)                          # 階乗から階乗の逆元を計算。フェルマーの小定理より、　a^-1 = a^(p-2) (mod p) if p = prime number and p and a are coprime
                                                        # python の pow 関数は自動的に mod の下での高速累乗を行ってくれる
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):                   # 上記の階乗の逆元から階乗の逆元のリストを生成（＝ facinv ）
            f = f * i % MOD
            facinv.append(f)
        facinv.reverse()

    def C(self, n, r):
        if not 0 <= r <= n: return 0                    # 範囲外という事はすなわち、そのような場合の数は無いはずなので、0を出力すればよい。（これが無いとREになる）
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def P(self, n, r):
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[n-r] % self.mod


#############################################################
N, M = map(int, input().split())
MOD=10 ** 9 + 7
C = Combination(M, MOD)
sgn = 1
res = 0
for k in range(0, N+1):
    res += sgn*C.C(N,k)*C.P(M-k,N-k)
    res %= MOD
    sgn *= -1
print(res*C.P(M,N)%MOD)

Submission status: Accepted

Solution code:
from functools import reduce

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

mod = 10 ** 9 + 7
ans = 0
c = 1
p1 = 1
p2 = reduce(lambda ac, v: ac * v % mod, range(m, m - n, -1), 1)
for i in range(n + 1):
    if i > 0:
        c = (c * (n - i + 1) * pow(i, mod - 2, mod)) % mod
        p1 = (p1 * (m - i + 1)) % mod
        p2 = (p2 * pow(m - i + 1, mod - 2, mod)) % mod
    x = c * p1 * (p2 ** 2)
    if i % 2 == 0:
        ans += x
    else:
        ans -= x
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
MOD=10**9+7
def facinv(N):
    fac,finv,inv=[0]*(N+1),[0]*(N+1),[0]*(N+1)
    fac[0]=1;fac[1]=1;finv[0]=1;finv[1]=1;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
    return fac,finv,inv

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

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

def p(r):
    return 1 if r%2 else -1

N,M=map(int,input().split())
fac,finv,inv=facinv(M)

ans=PER(M,N)**2%MOD
res=0
for r in range(1,N+1):
    f=COM(N,r)*PER(M,r)%MOD*(PER(M-r,N-r)**2%MOD)%MOD
    res=(res+(p(r)*f)+MOD)%MOD
print((ans-res+MOD)%MOD)

Submission status: Accepted

Solution code:
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]

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

Submission status: Accepted

Solution code:
MOD=10**9+7
def facinv(N):
    fac,finv,inv=[0]*(N+1),[0]*(N+1),[0]*(N+1)
    fac[0]=1;fac[1]=1;finv[0]=1;finv[1]=1;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
    return fac,finv,inv

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

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

N,M=map(int,input().split())
fac,finv,inv=facinv(M)

ans=PER(M,N)**2%MOD
res=0
for r in range(1,N+1):
    f=COM(N,r)*PER(M,r)%MOD*(PER(M-r,N-r)**2%MOD)%MOD
    res=(res+(pow(-1,r-1)*f)+MOD)%MOD
print((ans-res+MOD)%MOD)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

def cmb(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 p(n, r):
    return g1[n] * g2[n-r] % MOD

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

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

def solve():
    N, M = map(int, input().split())
    ans = 0
    for k in range(N+1):
        x = 0
        tmp = p(M-k, N-k)
        x = cmb(N, k) * p(M, k) * tmp * tmp
        if k%2==1:
            x *= -1
        ans = (ans + x) % MOD
    print(ans)

solve()

Submission status: Accepted

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

def calc(n):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= mod
        factorials.append(f)
    inv = pow(f, mod - 2, mod)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= mod
        invs[m - 1] = inv
    return factorials, invs

factorials, invs = calc(M)
mPn = (factorials[M] * invs[M - N]) % mod
ans = (mPn * mPn) % mod
for k in range(1, N + 1):
    v = pow(-1, k - 1) * factorials[N] * factorials[M - k] * invs[N - k] * invs[k] * invs[M - N] % mod
    ans -= v * mPn
print(ans % mod)

Submission status: Accepted

Solution code:
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
        

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

MOD = 10 ** 9 + 7
modFacts, invs = prepare(max(N, M))

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

print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

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

def fact_table(N, mod):
    inv = np.empty(N, np.int64)
    inv[0] = 0
    inv[1] = 1

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

    fact = np.empty(N, np.int64)
    fact[0] = 1
    for n in range(1,N):
        fact[n] = n * fact[n-1] % mod
    fact_inv = np.empty(N, np.int64)
    fact_inv[0] = 1
    for n in range(1,N):
        fact_inv[n] = fact_inv[n-1] * inv[n] % mod
    return fact, fact_inv, inv

def main():
    n, m = map(int, readline().split())
    mod = 10**9 + 7
    fact, fact_inv, inv = fact_table(n+1, mod)
    comb = fact[n] * fact_inv % mod * fact_inv[::-1] % mod
    comb[1::2] *= (-1)
    comb = comb[::-1]

    p = 1
    ans = 0
    for k in range(n+1):
        ans += comb[k] * p % mod
        if k != n:
            p = p * (m-n+1+k)%mod
    ans %= mod
    print( p * ans % mod )
    return

main()

Submission status: Accepted

Solution code:
MAX = 5 * (10**5)
MOD = 10**9 + 7

_fact = [1,1] + [0] * MAX
_inv = [0,1] + [0] * MAX
_fact_inv = [1,1] + [0] * MAX
for k in range(2, MAX + 1):
    _fact[k] = _fact[k-1] * k % MOD
    _inv[k] = (-_inv[MOD % k] * (MOD // k)) % MOD
    _fact_inv[k] = _fact_inv[k-1] * _inv[k] % MOD

def P(m, n):
    return _fact[m] * _fact_inv[m-n] % MOD

def C(m, n):
    return _fact[m] * _fact_inv[m-n] * _fact_inv[n] % MOD

def solve(n, m):
    res = 0
    for k in range(n+1):
        sign = 1 - 2 * (k%2)
        cur = sign * C(n, k) * P(m, k) * (P(m-k, n-k) ** 2)
        res = (res + cur) % MOD
    return res

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

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
def comb(n, r):
    if n < r:return 0
    if n < 0 or r < 0:return 0
    return fa[n] * fi[r] % mod * fi[n - r] % mod
def per(n, r):
    if n < r:return 0
    if n < 0 or r < 0:return 0
    return fa[n] * fi[n - r] % mod
n, m = map(int, input().split())
fa = [1] * (m + 1)
fi = [1] * (m + 1)
for i in range(1, m + 1):
    fa[i] = fa[i - 1] * i % mod
    fi[i] = pow(fa[i], mod - 2, mod)
ans = 0
for i in range(n + 1):
    if i % 2 == 0:
        ans += comb(n, i) * per(m, i) % mod * (per(m - i, n - i) ** 2) % mod
        ans %= mod
    else:
        ans += comb(n, i) * -1 * per(m, i) % mod * (per(m - i, n - i) ** 2) % mod
        ans % mod
print(ans % mod)

Submission status: Accepted

Solution code:
N, M=list(map(int,input().split()))
p=10**9+7
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
for i in range(2, M+1):
    fact.append((fact[-1] * i) % p) # [-1]は後ろから?
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return (fact[n] * factinv[r] * factinv[n-r]) % p
def pmt(n,r,p):
    if (r < 0) or (n < r):
        return 0
    return (fact[n] * factinv[n-r]) % p
C=0
for s in range(N+1):
    C=(C+(-1)**s*cmb(N,s,p)*pmt(M,N,p)*pmt(M-s,N-s,p)) %p
print(C)

Submission status: Accepted

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

mod = 10**9+7
N = 10**6  # N!まで求める
fact  = [1, 1]  # 階乗の元テーブル
fact_inv = [1, 1]  # 階乗の逆元テーブル
inv = [0, 1]  # 逆元テーブル計算用テーブル 1,2,,...の逆元を求めてる

# 計算 O(1)
def comb(n, r, mod):
    if (r<0 or r>n):
        return 0
    r = min(r, n-r)
    return fact[n] * fact_inv[r] * fact_inv[n-r] % mod

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

# 前処理 O(n)
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod//i)) % mod)
    fact_inv.append((fact_inv[-1] * inv[-1]) % mod)

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

print(ans)

Submission status: Accepted

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

# f = 1
# mod_factorial = [1] + [(f := f * i % MOD) for i in range(1, M+1)]
mod_factorial = [1]
for i in range(1, M+1):
    mod_factorial.append(mod_factorial[-1] * i % MOD)

mod_fact_inv = [pow(x, MOD-2, MOD) for x in mod_factorial]

def modperm(n, k):
    return mod_factorial[n] * mod_fact_inv[n-k] % MOD

def modcomb(n, k):
    return modperm(n, k) * mod_fact_inv[k] % MOD

sigma = 0
for i in range(N+1):
    x = modcomb(N, i)
    x %= MOD
    x *= modperm(M, i)
    x %= MOD
    x *= modperm(M-i, N-i)
    x %= MOD
    x *= modperm(M-i, N-i)
    x %= MOD
    x *= -1 if i&1 else 1
    sigma += x

sigma %= MOD
print(sigma)

Submission status: Accepted

Solution code:
mod=10**9+7
n=10**6
inv_t=[0]+[1]
for i in range(2,n):
  inv_t+=[inv_t[mod%i]*(mod-int(mod/i))%mod]

kai=[1,1]
rev_kai=[1,inv_t[1]]
for i in range(2,n):
  kai.append(kai[-1]*i%mod)
  rev_kai.append(rev_kai[-1]*inv_t[i]%mod)

def cmb(n,r):
  return kai[n]*rev_kai[r]*rev_kai[n-r]%mod

def prm(n,r):
  return kai[n]*rev_kai[n-r]%mod

N,M=map(int, input().split())
def f(x):
  e=cmb(N,x)*prm(M,x)*prm(M-x,N-x)*prm(M-x,N-x)
  e%=mod
  return e

ans=0
for i in range(N+1):
  g=f(i)*((-1)**i)
  ans+=g
print(ans%mod)

Submission status: Accepted

Solution code:
MOD = 1000000007
class mint:
    def __init__(self,x=0):
        self.x = x % MOD
    def __str__(self):
        return str(self.x)

    __repr__ = __str__

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

MAX = 1000005
fac = [1,1]
finv = [1,1]
inv = [0,1]
def COMinit():
    for i in range(2,MAX):
        fac.append((fac[-1] * i) % MOD)
        inv.append((-inv[MOD%i] * (MOD//i)) % MOD)
        finv.append((finv[-1] * inv[-1]) % MOD)

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

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

N,M = map(int, input().split())
COMinit()
res = mint(0)
now = mint()
for i in range(N+1):
    now = COM(N, i)
    now *= P(M-i, N-i)
    if(i%2 == 1):
        now = -1 * now
    res += now
res *= P(M, N)
print(res)

Submission status: Accepted

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

#階乗
F = 10**6+5
mod = 10**9+7
fact = [1]*F
inv = [1]*F
for i in range(2,F):
    fact[i]=(fact[i-1]*i)%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(F-2,1,-1):
    inv[i] = (inv[i+1]*(i+1))%mod
def comb(n,k):
    ans=(fact[n]*inv[n-k])%mod
    return (ans*inv[k])%mod

ans=0
for i in range(1,n+1):
    tmp=fact[m-i]*inv[m-n]*comb(n,i)
    ans+=(1 if i%2==1 else -1)*tmp
    ans%=mod
ans=fact[m]*inv[m-n]-ans
ans%=mod
ans*=fact[m]*inv[m-n]
ans%=mod

print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def S(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007


class FactInv:
    def __init__(self, N, MOD=1000000007):
        fact = [1]*(N+1)
        for i in range(1, N+1):
            fact[i] = fact[i - 1] * i % MOD

        inv = [None]*(N+1)
        inv[N] = pow(fact[N], MOD - 2, MOD)

        for i in range(N)[::-1]:
            inv[i] = inv[i + 1] * (i + 1) % MOD

        self.N = N
        self.MOD = MOD
        self.fact = fact
        self.inv = inv

    def perm(self, a, b):
        if a > self.N or b > self.N:
            raise ValueError(
                "\nPermutaion arguments are bigger than N\n N = {}, a = {}, b = {}".format(self.N, a, b))
        return self.fact[a] * self.inv[a-b] % self.MOD

    def comb(self, a, b):
        if a > self.N or b > self.N:
            raise ValueError(
                "\nCombination arguments are bigger than N\n N = {}, a = {}, b = {}".format(self.N, a, b))
        return self.fact[a] * self.inv[b] * self.inv[a-b] % self.MOD


def main():
    N, M = LI()
    factinv = FactInv(M)

    a = factinv.perm(M, N)

    tmp = a
    for k in range(1, N + 1):
        tmp = (tmp + factinv.comb(N, k) * factinv.perm(M - k, N - k) * pow(-1, k)) % MOD

    print(a * tmp % MOD)





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
from functools import reduce


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

inv_t = [0] + [1]
for i in range(2, N):
    inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]

kai = [1, 1]
rev_kai = [1, inv_t[1]]
for i in range(2, N):
    kai.append(kai[-1] * i % mod)
    rev_kai.append(rev_kai[-1] * inv_t[i] % mod)

def cmb(n, r):
    return kai[n] * rev_kai[r] * rev_kai[n - r] % mod

def prm(n, r):
    return kai[n] * rev_kai[n - r] % mod

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

a = 0
for k in range(n+1):
    a += prm(m, k)*prm(m-k,n-k)**2*(-1)**k*cmb(n,k) % mod

print(a % mod)

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

class modfact(object):
    def __init__(self, n):
        fact, invfact = [1] * (n + 1), [1] * (n + 1)
        for i in range(1, n + 1): fact[i] = i * fact[i - 1] % MOD
        invfact[n] = pow(fact[n], MOD - 2, MOD)
        for i in range(n - 1, -1, -1): invfact[i] = invfact[i + 1] * (i + 1) % MOD
        self._fact, self._invfact = fact, invfact

    def fact(self, n):
        return self._fact[n]

    def invfact(self, n):
        return self._invfact[n]

    def comb(self, n, k):
        return self._fact[n] * self._invfact[k] % MOD * self._invfact[n - k] % MOD if 0 <= k <= n else 0

    def perm(self, n, k):
        return self._fact[n] * self._invfact[n - k] % MOD if 0 <= k <= n else 0

def resolve():
    n, m = map(int, input().split())
    mf = modfact(m)
    ans = 0
    for k in range(n + 1):
        if k & 1:
            ans -= mf.comb(n, k) * mf.perm(m - k, n - k)
        else:
            ans += mf.comb(n, k) * mf.perm(m - k, n - k)
        ans %= MOD
    ans *= mf.perm(m, n)
    ans %= MOD
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
MAX = 10 ** 6
MOD = 10 ** 9 + 7

fac = [0 for i in range(MAX)]
finv = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]

def comInit(mod):
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 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 com(n, r, mod):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod

def p(n, r, mod):
    return fac[n] * finv[n - r] % mod

comInit(MOD)

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

ans = 0
for i in range(N + 1):
    now = com(N, i, MOD)
    now *= p(M - i, N - i, MOD)
    if i & 1 > 0:
        now = -now
    ans += now

ans *= p(M, N, MOD)
print(ans % MOD)

Submission status: Accepted

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

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

#逆元テーブル
inv_t = [0]+[1]
for i in range(2, N):
    inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]

#階乗計算
kai = [1, 1]
rev_kai = [1, inv_t[1]]
for i in range(2, N):
    kai.append(kai[-1] * i % mod)
    rev_kai.append(rev_kai[-1] * inv_t[i] % mod)

# コンビネーション計算
def cmb(n, r):
    return kai[n] * rev_kai[r] * rev_kai[n-r] % mod

def prm(n, r):
    return kai[n] * rev_kai[n-r] % mod

ans = 0
tmp = 1

# 包除原理に従って場合の数を求める
for k in range(n+1):
    #　!(Ai != Bi)、つまり　Ai == Bi　という条件N個からK個選び
    # それらの条件の「かつ」の条件を満たす場合の数考える
    ans += tmp * cmb(n, k) * prm(m-k, n-k) % mod # KはAと一致するように決めて、残りのN-K箇所を自由に決める
    ans %= mod
    tmp *= -1

# Aの選び方をかける
ans *= prm(m, n)
ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import sys
N,M=map(int, sys.stdin.readline().split())

mod=10**9+7
fact, inv_fact=[1], [1]
fact_tmp=1
for i in range(1, M+1):
    fact_tmp*=i
    fact_tmp%=mod
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, mod-2, mod))

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

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

ans=0
for k in range(N+1):
    if k%2==0: ans+=ncr(N,k)*ncr(M,k)*npr(k,k)*(npr(M-k,N-k)**2)
    else:      ans-=ncr(N,k)*ncr(M,k)*npr(k,k)*(npr(M-k,N-k)**2)
    ans%=mod
print ans

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
N,M=map(int, sys.stdin.readline().split())

mod=10**9+7
fact, inv_fact=[1], [1]
fact_tmp=1
for i in range(1, M+1):
    fact_tmp*=i
    fact_tmp%=mod
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, mod-2, mod))

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

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

ans=0
for k in range(N+1):
    if k%2==0: ans+=ncr(N,k)*ncr(M,k)*npr(k,k)*(npr(M-k,N-k)**2)
    else:      ans-=ncr(N,k)*ncr(M,k)*npr(k,k)*(npr(M-k,N-k)**2)
    ans%=mod
print ans

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
mod = 10**9 + 7
def setfact(l, mod):
    global fact
    global ifact
    fact = [1]
    for i in range(1, l+1):
        fact.append(fact[-1]*i%mod)
    ifact = [0] * (l+1)
    ifact[-1] = pow(fact[-1], mod-2, mod)
    for i in range(l, 0, -1):
        ifact[i-1] = ifact[i] * i %mod
def comb(n, m, mod):
    global fact
    global ifact
    return fact[n]*ifact[n-m]*ifact[m]%mod
def p(n, m, mod):
    global fact
    global ifact
    return fact[n]*ifact[n-m]%mod
ans = 0
setfact(m, mod)
for k in range(n+1):
    ans += p(m-k, n-k, mod)*comb(n, k, mod) * (-1)**k
    ans %= mod
    if ans < 0:
        ans += mod
ans *= p(m, n, mod)
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
class Factorial():
    def __init__(self, n, mod):
        self.mod = mod
        self.fct = [0 for _ in range(n + 1)]
        self.inv = [0 for _ in range(n + 1)]
        self.fct[0] = 1
        self.inv[0] = 1
        for i in range(n):
            self.fct[i + 1] = self.fct[i] * (i + 1) % mod
        self.inv[n] = pow(self.fct[n], mod - 2, mod)
        for i in range(n)[::-1]:
            self.inv[i] = self.inv[i + 1] * (i + 1) % mod

    def fact(self, m):
        return self.fct[m]

    def invf(self, m):
        return self.inv[m]

    def perm(self, m, k):
        if m < k: return 0
        return self.fct[m] * self.inv[m - k] % self.mod

    def comb(self, m, k):
        if m < k: return 0
        return self.fct[m] * self.inv[k] * self.inv[m - k] % self.mod

MOD = 1000000007

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

f = Factorial(M, MOD)

res = f.perm(M, N)

for k in range(1, N + 1):
    res -= (-1)**(k - 1) * f.comb(N, k) * f.perm(M - k, N - k)

res *= f.perm(M, N)
res %= MOD

print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

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

def COMinit(n,MOD):
    fac,finv,inv=[0]*max(2,n+1),[0]*max(2,n+1),[0]*max(2,n+1)
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    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
    return fac,finv,inv

fac,finv,inv=COMinit(M,MOD)

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

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

ans=0
k=1

for i in range(N+1):
    ans+=k*COM(N,i)*PER(M,i)*(PER(M-i,N-i)**2)
    ans%=MOD
    k*=-1
print(ans)

Submission status: Accepted

Solution code:
#写経
#https://atcoder.jp/contests/abc172/submissions/14794920

MOD = 10**9 + 7

def resolve():
    N,M = map(int,input().split())
    a = 1
    d = [1]
    for i in range(N):
        d.append(((M-N+i)*d[i]+i*d[i-1])%MOD)
        a=a*(M-i)%MOD
    print(a*d[-1]%MOD)
resolve()

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 個位置，使這些位置不同的方法數」、…、「選定 x 個位置，使這些位置不同的方法數」，即
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)

f_N = 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 = (-1)**((N - i) % 2) * tool.comb(N, i) % mod * g_i % mod
    f_N = (f_N + val) % mod
ans = tool.comb(N, N) * f_N % mod
print(ans)

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 個位置，使這些位置不同的方法數」、…、「選定 x 個位置，使這些位置不同的方法數」，即
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)

f_N = 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 = (-1)**((N - i) % 2) * tool.comb(N, i) % mod * g_i % mod
    f_N = (f_N + val) % mod
ans = tool.comb(N, N) * f_N % mod
print(ans)

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)

f_N = 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 = (-1)**((N - i) % 2) * tool.comb(N, i) % mod * g_i % mod
    f_N = (f_N + val) % mod
ans = tool.comb(N, N) * f_N % mod
print(ans)