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:
import sys

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

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


class CombMod:

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

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

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

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

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

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

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

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


def main():

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

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

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

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

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

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

        ans += t
        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import numpy as np

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

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


class CombMod:

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

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

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

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

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

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

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

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


def main():

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

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

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

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

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

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

        ans += t
        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

Solution code:
# ライブラリ改変テスト
class Combi():
    def __init__(self, N, mod):
        self.power = [1 for _ in range(N+1)]
        self.rev = [1 for _ in range(N+1)]
        self.mod = mod
        for i in range(2, N+1):
            self.power[i] = (self.power[i-1]*i) % self.mod
        self.rev[N] = pow(self.power[N], self.mod-2, self.mod)
        for j in range(N, 0, -1):
            self.rev[j-1] = (self.rev[j]*j) % self.mod

    def com(self, K, R):
        if K < R:
            return 0
        else:
            return ((self.power[K])*(self.rev[K-R])*(self.rev[R])) % self.mod

    def pom(self, K, R):
        if K < R:
            return 0
        else:
            return (self.power[K])*(self.rev[K-R]) % self.mod


N, M = map(int, input().split())
mod = 10**9+7
c = Combi(10**6, mod)
ans = c.pom(M, N)**2 % mod
for k in range(1, N+1):
    s = (-1)**((k-1) % 2)
    t = c.com(N, k)
    u = (c.pom(M-k, N-k)**2) % mod
    v = c.pom(M, k) % mod
    ans -= s*t*u*v
print(ans % mod)

Submission status: Accepted

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

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

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

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

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

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

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

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

Submission status: Accepted

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

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

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

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

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

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

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

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

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

print(e_neq())

Submission status: Accepted

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

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

mod = 10**9+7               # mod素数
N = 10**6                   # 出力の制限
g1 = [1]*(N+1)              # 元テーブル
g2 = [1]*(N+1)              # 逆元テーブル
for i in range(2, N + 1 ): # 準備
    g1[i] = ( g1[i-1] * i ) % mod
g2[N] = pow(g1[-1], mod-2, mod)
for i in range(N, 0, -1):
    g2[i-1] = ( g2[i] * i ) % mod

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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

fac = [1, 1]
finv = [1, 1]
inv = [0, 1]
for i in range(2, max(N + 1, M + 1)):
    fac.append((fac[-1] * i) % mod)
    inv.append((-inv[mod%i] * (mod//i)) % mod)
    finv.append((finv[-1] * inv[-1]) % mod)
ans = 0
for i in range(N+1):
    ans += (-1)**i * ((comb(N, i, mod) * perm(M, i, mod))%mod * (perm(M-i, N-i, mod)**2)%mod)%mod
    ans %= mod
print(ans)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

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

fac = [1, 1]
finv = [1, 1]
inv = [0, 1]
for i in range(2, max(N + 1, M + 1)):
    fac.append((fac[-1] * i) % mod)
    inv.append((-inv[mod%i] * (mod//i)) % mod)
    finv.append((finv[-1] * inv[-1]) % mod)
c = comb(M, N, mod)
ans = ((fac[N] * c % mod) ** 2) % mod

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

Submission status: Accepted

Solution code:
# @author 

import sys

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

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

        # op = [2, 3, 4, 5, 1, 6]
        # # op = [1, 2, 3, 4, 5, 6]
        # cnt = 0
        # for p in permutations(range(1, 7)):
        #     for i in range(6):
        #         if op[i] == p[i]:
        #             break
        #     else:
        #         cnt += 1
        #
        # print(cnt)

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

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

        print(ans)

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

solver.solve()

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ans = 0
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


mod = 10**9+7
N = 500001
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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


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

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

Submission status: Accepted

Solution code:
import numpy as np

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

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

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


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


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


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

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

Submission status: Accepted

Solution code:
import sys

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

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

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

# 包除原理
# 2つめの条件は常に成り立った状況で考える
# {1,…,N}の部分集合Sの元iに対してA_i=B_iが成り立つようなA_1,…,B_1,…の組の個数を考える
ans = a**2 % mod
r = ans
for i in range(1,N+1):
    r *= (N-i+1)
    r %= mod
    r *= pow(i,mod-2,mod)
    r %= mod
    r *= pow(M-i+1,mod-2,mod)*(-1)
    r %= mod
    ans += r
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import sys

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

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

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

# 包除原理
# 2つめの条件は常に成り立った状況で考える
# {1,…,N}の部分集合Sの元iに対してA_i=B_iが成り立つようなA_1,…,B_1,…の組の個数を考える
ans = a**2 % mod
r = ans
for i in range(1,N+1):
    r *= (N-i+1)*pow(i,mod-2,mod)*pow(M-i+1,mod-2,mod)*(-1)
    r %= mod
    ans += r
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

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


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


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


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

print(ans)

Submission status: Accepted

Solution code:
import sys

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

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

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

# 包除原理
# 2つめの条件は常に成り立った状況で考える
# {1,…,N}の部分集合Sの元iに対してA_i=B_iが成り立つようなA_1,…,B_1,…の組の個数を考える
ans = a**2 % mod
r = ans
for i in range(1,N+1):
    r *= (N-i+1)*pow(i,-1,mod)*pow(M-i+1,-1,mod)*(-1)
    r %= mod
    ans += r
    ans %= mod

print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

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

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

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

      print(Ans)
      #print(Perm)
      return 0

if __name__ == "__main__":
      solve()

Submission status: Accepted

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

MAX = 5 * 10 ** 5

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

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

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


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


p1 = 1
p2 = 1

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

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

    p1 *= m - i
    p1 %= mod

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

print(ans)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
mod = 10**9+7
M = 5*10**5

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

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
mod = 10**9+7
d = m-n
#mPn
p = 1
for i in range(n):
  p *= m-i
  p %= mod
dp = [0,1]
for i in range(n):
  tmp = dp[-2]*i + dp[-1]*(i+d)
  tmp %= mod
  dp.append(tmp)
#print(dp)
p *= dp[-1]
p %= mod
print(p)

Submission status: Accepted

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

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

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

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

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

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

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


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


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

Submission status: Accepted

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

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


# print(ans)
prev = 1
ansB = M-1


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

# print(ansB)

print((ans*ansB) % mod)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 10**9 + 7
MAX_N = 10**6

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

fac_inv = [1] + [0] * MAX_N
# Femrmat's little theorem says a**(p-1) mod p == 1
# then, a * a**(p-2) mod p == 1
# it means that a**(p-2) is the inverse element
# Here, Get 1 / n! first
fac_inv[MAX_N] = pow(fac[MAX_N], MOD-2, MOD)
for i in range(MAX_N, 1, -1):
    fac_inv[i-1] = fac_inv[i] * i % MOD

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

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

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

Submission status: Accepted

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

# N = 4

# for M in range(N, N+5):
#     P = list(permutations(range(M),N))
#     #print(P)
#     ans = 0
#     for A in P:
#         ok = True
#         for i, a in enumerate(list(A)):
#             if i == a:
#                 ok = False
#                 break
#         if ok:
#             ans += 1
#     print(ans)

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

# コンビネーション
mod = 10**9+7
def cmb(n, r, mod=mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NN = 6*10**5 # 使うデータによって変える
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

# a(n) = sum((-1)^i*binomial(3,i)*(n-i)!/(n-3)!,i=0..3).

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

Submission status: Accepted

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

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

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

cominit()

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

Submission status: Accepted

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

nA = 1

for i in range(N):
  nA *= M - i
  nA %= mod_

dp = [0 for i in range(N+1)]
dp[1] = M-N
if N == 1:
  print( nA * dp[N] % mod_ )  
else:
  dp[2] = M - N + 1 + (M - N)*(M - N)
  dp[1] %= mod_
  dp[2] %= mod_
  for i in range(3, N+1):
    dp[i] = dp[i-1] * (M - N + i - 1) + dp[i-2] * (i-1)
    dp[i] %= mod_
  print( nA * dp[N] % mod_ )

Submission status: Accepted

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

g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
for i in range(2,5*10**5+1): # <- どこまでfor文を回すかは問題次第, 2*10**6くらいまでならpypyなら間に合う
    g1.append((g1[-1] * i) % MOD)
    inverse.append((-inverse[MOD % i] * (MOD // i)) % MOD)
    g2.append((g2[-1] * inverse[-1]) % MOD)

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

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


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

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

print((ans*base) % MOD)