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:
# 解説AC 包除原理 外側を数えるのが難しいとき, 完全順列
n, m = map(int, input().split())
mod = 10 ** 9 + 7


def table():
    k = 5 * 10**5 + 5  # 変える
    fac = [1] * k
    finv = [1] * k
    inv = [0] * k
    inv[1] = 1
    for i in range(2, k):
        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


fac, finv = table()


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


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


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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
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

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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):
        # nCk
        tmp = (a[N] * inva[N-k] % p) * inva[k] % p
        # (-1)**k
        if k % 2 == 1:
            tmp = -tmp % p
        # mPk
        tmp = (tmp * a[M] % p) * inva[M-k] % p

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

MOD = 10**9 + 7
MAX = m + 1
fact = [1] * (MAX + 1)  # i!
finv = [1] * (MAX + 1)  # (i!)^{-1}
iinv = [1] * (MAX + 1)  # i^{-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)

Submission status: Accepted

Solution code:

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
        # 1/n!を逆元で求める
        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)

Submission status: Accepted

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

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
        

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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    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)    # a ^ p-2 ≡ 1/a (mod p) において a = n! とする。 1/n! (mod p) を求める
        for i in range(size-1, -1, -1):
            inv_fact_mod[i] = (inv_fact_mod[i+1] * (i+1)) % mod    # 1/(n-1)! = 1/n! * n
        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:
            # pow はすでに繰り返し二乗法で効率的に実装されている
            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)

    # Σ {k=0 to n} (nCk * (-1)^k * mPk * (m-kPn-k)^2)
    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()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
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

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
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):#0~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):#0~nの階乗のmodに関する逆元を求める
        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)

Submission status: Accepted

Solution code:
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)]  # N_C_k
    perm_1 = [1 for _ in range(N + 1)]  # M_P_k
    perm_2 = [1 for _ in range(N + 1)]  # (M-k)_P_(N-k)
    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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

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

#############
# Functions #
#############

######INPUT######
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)]

######OUTPUT######
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()

#####Shorten#####
def DD(arg): return defaultdict(arg)

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

######Combination######
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

######Factorization######
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

#####MakeDivisors######
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

#####MakePrimes######
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

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

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

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

#####ChangeBase#####
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]

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

#############
# Main Code #
#############
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)

Submission status: Accepted

Solution code:
# 一致している数の集合をSとする。
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
# i個共通とする.共通じゃないのはmからn-i個
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)

Submission status: Accepted

Solution code:
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(mod_inverse(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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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 = 10**6+10 # 必要なテーブルサイズ
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 # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    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)

Submission status: Accepted

Solution code:
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)
  #print(temp)
  ans = (ans-temp)%MOD
print(ans)