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: Time Limit Exceeded

Solution code:
#

import sys
input=sys.stdin.readline
MOD=10**9+7

fac=[1]*(5*10**5+1)
for i in range(1,5*10**5+1):
    fac[i]=(fac[i-1]*i)%MOD
    
def inv(x):
    return pow(x,MOD-2,MOD)

def nPr(n,r):
    return (fac[n]*inv(fac[n-r]))%MOD
def nCr(n,r):
    return (fac[n]*inv(fac[n-r])*inv(fac[r]))%MOD

def main():
    N,M=map(int,input().split())
    hojo=0
    for i in range(1,N+1):
        hojo+=(-1)**(i)*nCr(N,i)*nPr(M,i)*nPr(M-i,N-i)**2
        hojo%=MOD
    print((nPr(M,N)**2+hojo)%MOD)
    
    
    
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

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

    tmp2 = ansB - tmp
    # print(tmp2)

    ansB = tmp * (M-i) + (tmp2)*(M-i-1)
    # print(tmp, tmp2)
    # ansB = tmp + tmp2
    ansB %= mod
    prev = tmp2
    # print(ansB)
# print(ansB)

print((ans*ansB) % mod)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
mod = 10**9 + 7
# 一個数列が決まった場合に、その数列と同じ数字が同じ場所にあるものが禁止される。


MPN = [0]*M
MPN[0] = M
for i in range(M-1, 0, -1):
    MPN[M - i] = MPN[M-1-i]*i % mod

ans = MPN[N-1]
# print(ans)
prev = 1
ansB = M-1

for i in range(1, N):
    tmp = (prev)*i

    tmp2 = ansB - tmp
    # print(tmp2)

    ansB = tmp * (M-i) + (tmp2)*(M-i-1)
    # print(tmp, tmp2)
    # ansB = tmp + tmp2
    ansB %= mod
    prev = tmp2
    # print(ansB)
# print(ansB)

print((ans*ansB) % mod)

Submission status: Time Limit Exceeded

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

import math

MODULUS = 10**9 + 7

def make_nCr_mod(max_n=5 * 10**5 + 100, mod=10**9 + 7):
    fact, inv_fact = [0] * (max_n + 1), [0] * (max_n + 1)
    fact[0] = 1
    for i in range(max_n):
        fact[i + 1] = fact[i] * (i + 1) % mod

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

    def nCr_mod(n, r):
        res = 1
        while n or r:
            a, b = n % mod, r % mod
            if a < b:
                return 0
            res = res * fact[a] % mod * inv_fact[b] % mod * inv_fact[a - b] % mod
            n //= mod
            r //= mod
        return res

    return nCr_mod

nCr_mod = make_nCr_mod()

from types import GeneratorType

def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

memo = dict()

@bootstrap
def f(n, m):
    assert(m >= n)
    if n < 0 or m < 0:
        yield 0
    if n == 0 or m == 0:
        yield 1

    key = (n,m)

    if key in memo:
        yield memo[key]

    t1 = yield f(n-2, m-2)
    t2 = yield f(n-1, m-1)
    t3 = yield f(n-1, m-1)
    ret = (n-1)*(t1 + t2) + (m-n)*t3
    ret = ret % MODULUS

    memo[key] = ret

    yield ret

def ans(N, M):
    return nCr_mod(M, N)*(math.factorial(N) % MODULUS)*f(N,M) % MODULUS

N, M = input().split(' ')
N = int(N)
M = int(M)
print(ans(N, M))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
mod = 10**9 + 7
# 一個数列が決まった場合に、その数列と同じ数字が同じ場所にあるものが禁止される。


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


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)


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)


MPN = [0]*M
MPN[0] = M
for i in range(M-1, 0, -1):
    MPN[M - i] = MPN[M-1-i]*i % mod

ans = MPN[N-1]
# print(ans)
prev = 1
ansB = M-1

for i in range(1, N):
    tmp = (prev)*i

    tmp2 = ansB - tmp
    # print(tmp2)

    ansB = tmp * (M-i) + (tmp2)*(M-i-1)
    # print(tmp, tmp2)
    # ansB = tmp + tmp2
    ansB %= mod
    prev = tmp2
    # print(ansB)
# print(ansB)

print((ans*ansB) % mod)

Submission status: Time Limit Exceeded

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

import math

MODULUS = 10**9 + 7

def make_nCr_mod(max_n=2 * 10**6, mod=10**9 + 7):
    fact, inv_fact = [0] * (max_n + 1), [0] * (max_n + 1)
    fact[0] = 1
    for i in range(max_n):
        fact[i + 1] = fact[i] * (i + 1) % mod

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

    def nCr_mod(n, r):
        res = 1
        while n or r:
            a, b = n % mod, r % mod
            if a < b:
                return 0
            res = res * fact[a] % mod * inv_fact[b] % mod * inv_fact[a - b] % mod
            n //= mod
            r //= mod
        return res

    return nCr_mod

nCr_mod = make_nCr_mod()

from types import GeneratorType

def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

memo = dict()

@bootstrap
def f(n, m):
    assert(m >= n)
    if n < 0 or m < 0:
        yield 0
    if n == 0 or m == 0:
        yield 1

    key = (n,m)

    if key in memo:
        yield memo[key]

    t1 = yield f(n-2, m-2)
    t2 = yield f(n-1, m-1)
    t3 = yield f(n-1, m-1)
    ret = (n-1)*(t1 + t2) + (m-n)*t3
    ret = ret % MODULUS

    memo[key] = ret

    yield ret

def ans(N, M):
    return nCr_mod(M, N)*(math.factorial(N) % MODULUS)*f(N,M) % MODULUS

N, M = input().split(' ')
N = int(N)
M = int(M)
print(ans(N, M))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque
import heapq
import itertools
from decimal import Decimal
import bisect
from operator import itemgetter
MAX_INT = int(10e18)
MIN_INT = -MAX_INT
mod = 1000000000+7
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

import functools
@functools.lru_cache(maxsize=None)
def combi(n, r):
  r = min(r, n-r)
  numer = denom = 1
  for i in range(1, r+1):
    numer = numer * (n+1-i) %mod
    denom = denom * i %mod
  return numer * pow(denom, mod-2, mod) %mod

def tami(n, r):
  if r == 0:
    res = kaizyou[n]
    return res %mod
  elif r == 1:
    res = kaizyou[n-1] * (n-1)
    return res %mod
  else:
    return (tami(n-1, r-1) + tami(n-1, r-2) )%mod

N,M = IL()

kaizyou = [0,1]
for i in range(2,N+1):
  kaizyou.append(kaizyou[-1]*i %mod)

ans = 0
for i in range(max(0, 2*N-M), N+1):
  ans += ((combi(N, i) * combi(M-N, N-i) ) %mod * tami(N, i)) %mod
print((((combi(M, N) * kaizyou[N]) %mod) * ans) %mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque
import heapq
import itertools
from decimal import Decimal
import bisect
from operator import itemgetter
MAX_INT = int(10e18)
MIN_INT = -MAX_INT
mod = 1000000000+7
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def combi(n, r):
  r = min(r, n-r)
  numer = denom = 1
  for i in range(1, r+1):
    numer = numer * (n+1-i) %mod
    denom = denom * i %mod
  return numer * pow(denom, mod-2, mod) %mod

def tami(n, r):
  if r == 0:
    res = kaizyou[n]
    return res %mod
  elif r == 1:
    res = kaizyou[n-1] * (n-1)
    return res %mod
  else:
    return (tami(n-1, r-1) + tami(n-1, r-2) )%mod

N,M = IL()

kaizyou = [0,1]
for i in range(2,N+1):
  kaizyou.append(kaizyou[-1]*i %mod)

ans = 0
for i in range(max(0, 2*N-M), N+1):
  ans += ((combi(N, i) * combi(M-N, N-i) ) %mod * tami(N, i)) %mod
print((((combi(M, N) * kaizyou[N]) %mod) * ans) %mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque
import heapq
import itertools
from decimal import Decimal
import bisect
from operator import itemgetter
MAX_INT = int(10e18)
MIN_INT = -MAX_INT
mod = 1000000000+7
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def combi(n, r):
  r = min(r, n-r)
  numer = denom = 1
  for i in range(1, r+1):
    numer = numer * (n+1-i) %mod
    denom = denom * i %mod
  return numer * pow(denom, mod-2, mod) %mod

def tami(n, r):
  if r == 0:
    res = kaizyou[n]
    return res %mod
  elif r == 1:
    res = kaizyou[n-1] * (n-1)
    return res %mod
  else:
    return (tami(n-1, r-1) + tami(n-1, r-2) )%mod

N,M = IL()

kaizyou = [0,1]
for i in range(2,N+1):
  kaizyou.append(kaizyou[-1]*i %mod)

ans = 0
for i in range(max(0, 2*N-M), N+1):
  ans += (combi(M, N) %mod * (combi(N, i) * combi(M-N, N-i) ) %mod * tami(N, i)) %mod
print((kaizyou[N] * ans) %mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque
import heapq
import itertools
from decimal import Decimal
import bisect
from operator import itemgetter
MAX_INT = int(10e18)
MIN_INT = -MAX_INT
mod = 1000000000+7
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def combi(n, r):
  r = min(r, n-r)
  numer = denom = 1
  for i in range(1, r+1):
    numer = numer * (n+1-i) %mod
    denom = denom * i %mod
  return numer * pow(denom, mod-2, mod) %mod

def tami(n, r):
  if r == 0:
    res = kaizyou[n]
    return res %mod
  elif r == 1:
    res = kaizyou[n-1] * (n-1)
    return res %mod
  else:
    return (tami(n-1, r-1) + tami(n-1, r-2) )%mod

N,M = IL()

kaizyou = [0,1]
for i in range(2,N+1):
  kaizyou.append(kaizyou[-1]*i %mod)

ans = 0
for i in range(max(0, 2*N-M), N+1):
  ans += (combi(M, N) * (combi(N, i) * combi(M-N, N-i) ) %mod * tami(N, i)) %mod
print((kaizyou[N] * ans) %mod)

Submission status: Time Limit Exceeded

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

fac = [1 for _ in range(m+1)]
for i in range(m):
    fac[i+1] = fac[i] * (i+1) % mod
memo = [[-1 for _ in range(m+1)] for _ in range(n+1)]
for i in range(m+1):
    memo[1][i] = i-1

def g(n, m):
    if memo[n][m] != -1:
        return memo[n][m]
    
    memo[n][m] = (g(n-1, m-1) * n + fac[n-1] * (n-1)) % mod
    return memo[n][m]

ans = g(n, m)

tmp = m
for _ in range(n):
    ans *= tmp
    ans %= mod
    tmp -= 1

print(ans)

Submission status: Time Limit Exceeded

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

H=[[0 for i in range(11)] for j in range(11)]

L=[i+1 for i in range(M)]
import itertools
CMB=list(itertools.permutations(L,N))
count=0
for i in range(len(CMB)):
    for j in range(len(CMB)):
        flag=1
        for k in range(N):
            if CMB[i][k]==CMB[j][k]:
                flag=0
                break
        if flag:
            #print(CMB[i],CMB[j])
            count+=1
print(count%mod)

Submission status: Time Limit Exceeded

Solution code:
import math
def p(n, r):
    return math.factorial(n) // math.factorial(n - r)
def c(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
def q(n,m):
    if n==1:
        return m-1
    else:
        sub=p(m,n)-c(n,n)
        for i in range(1,n):
            sub-=c(n,i)*q(n-i,m-i)
        return sub
n,m = map(int,input().split())
print((p(m,n)*q(n,m))%(10**9+7))

Submission status: Time Limit Exceeded

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

Facts = [0]*(MAX+1)
Facts[0] = 1

f = 1
for i in range(1, MAX+1):
    f = f*i%MOD
    Facts[i] = f

def modPow(a, b):
    x = 1
    
    while b > 0:
        if b & 1:
            x = (x*a)%MOD

        a = (a**2)%MOD
        b //= 2

    return x


def modInv(x):
    return modPow(x, MOD-2)


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

a0 = Facts[M]*modInv(Facts[M-N])%MOD
a = a0
n = 1
b2 = Facts[M-N]

for i in range(1, N+1):
    n = n*(N-i+1)%MOD
    b2 = b2*i%MOD
    b = Facts[M-i]*n%MOD*modInv(b2)%MOD

    if i%2 == 1:
        b = -b

    a = a + b 

print(a*a0%MOD)

Submission status: Time Limit Exceeded

Solution code:
import math
def p(n, r):
    return math.factorial(n) // math.factorial(n - r)
def c(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def q(n,m):
    if n==1:
        return m-1
    else:
        sub=p(m,n)-c(n,n)
        for i in range(1,n):
            sub-=c(n,i)*q(n-i,m-i)
        return sub
n,m = map(int,input().split())
print((p(m,n)*q(n,m))%(10**9+7))

Submission status: Accepted

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

class mod_pack:

    def __init__(self, MOD, MAX):
        self.MOD = MOD
        self.MAX = MAX
        self.fac, self.ifac = [1]*(MAX+1), [1]*(MAX+1)
        for i in range(1, MAX+1):
            self.fac[i] = self.fac[i-1]*i % MOD
            self.ifac[i] = self.ifac[i-1] * self.mpow(i, MOD-2) % MOD
    
    def mpow(self, x, n):
        ans = 1
        while n!=0:
            if n&1: ans = ans*x % self.MOD
            x = x*x % self.MOD
            n = n >> 1
        return ans

    def mcomb(self, m, n):
        if (m==0 and n==0): return 1
        return (self.ifac[m-n] * self.ifac[n] % self.MOD) * self.fac[m] % self.MOD

    def mperm(self, m, n):
        if (m < n): return 0
        return self.ifac[m-n] * self.fac[m] % MOD
    

mp = mod_pack(10**9+7, M)

tot = mp.mperm(M, N)
ans = 0
for k in range(1, N+1):
#    print(k, mp.mcomb(N, k), mp.mperm(M-k, N-k))
    ans = (ans + (-1)**(k-1) * mp.mcomb(N, k) * mp.mperm(M-k, N-k)) % MOD


print((tot * (tot - ans))%MOD)

Submission status: Accepted

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

MOD = 10**9 + 7





def solve():
    N,M = map(int,input().split())
    # print(cntA*dp(M,N)%MOD)
    fac = [1,1] + [0] * M
    inv = [1,1] + [0] * M
    for i in range(2,M+1):
        fac[i] = (fac[i-1]*i)%MOD
    inv[M] = pow(fac[M],MOD-2,MOD)
    for i in range(M-1,1,-1):
        inv[i] = inv[i+1]*(i+1)%MOD
    def p(a,b):
        return (fac[b]*inv[b-a])%MOD
    def c(a,b):
        return (fac[b]*inv[a]*inv[b-a]) % MOD
    res = p(N,M)
    for i in range(1,N+1):
        res += (-1)**(i&1)*c(i,N)*p(N-i,M-i)
        res %= MOD
    print(res* p(N,M)%MOD)




if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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

MOD = 10**9+7
NUM = 10**6
g1 = [1, 1]
g2 = [1, 1]
inv = [0, 1]

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

def comb(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

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

ans = perm(m,n)**2
sub=0

for k in range(1,n+1):
    cnt = comb(n,k)*perm(m-k,n-k) % MOD
    if k%2==1:
        sub+=cnt
    else:
        sub-=cnt

sub*=perm(m,n)%MOD
ans-=sub
print(ans%MOD)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
fct = [1, 1]+[0]*m
mod = 10**9+7
for i in range(2, m+1):
    fct[i] = fct[i-1]*i
    fct[i] %= mod
inv = [1, 1]+[0]*m
invf = [1, 1]+[0]*m

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

ans = 0


def chs(x, y):
    return fct[x]*invf[y]*invf[x-y]
def chs2(x,y):
    return fct[x]*invf[x-y]

m_inv = pow(m, mod-2, mod)
mn = pow(m, n, mod)
for i in range(n+1):
    ans += ((-1)**(i % 2))* chs(n, i)*chs2(m-i,n-i)
    ans %= mod
    mn *= (m_inv)
    mn %= mod
    #print(ans,chs(n, i),chs2(m,n-i))
print(ans*chs2(m,n)%mod)

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


class ModInt:
    def __init__(self, x, MOD=1000000007): self.x, self.MOD = x % MOD, MOD
    def __str__(self): return str(self.x)
    def __add__(self, other): return ModInt(self.x + other.x) if isinstance(other, ModInt) else ModInt(self.x + other)
    def __sub__(self, other): return ModInt(self.x - other.x) if isinstance(other, ModInt) else ModInt(self.x - other)
    def __mul__(self, other): return ModInt(self.x * other.x) if isinstance(other, ModInt) else ModInt(self.x * other)
    def __truediv__(self, other): return ModInt(self.x * other.inverse()) if isinstance(other, ModInt) else ModInt(self.x * pow(other, self.MOD - 2, self.MOD))
    def __pow__(self, other): return ModInt(pow(self.x, other.x, self.MOD)) if isinstance(other, ModInt) else ModInt(pow(self.x, other, self.MOD))
    def __rsub__(self, other): return ModInt(other.x - self.x) if isinstance(other, ModInt) else ModInt(other - self.x)
    def __rtruediv__(self, other): return ModInt(other.x * other.inverse()) if isinstance(other, ModInt) else ModInt(other * pow(self.x, self.MOD - 2, self.MOD))
    def __rpow__(self, other): return ModInt(pow(other.x, self.x, self.MOD)) if isinstance(other, ModInt) else ModInt(pow(other, self.x, self.MOD))
    __repr__, __radd__, __rmul__ = __str__, __add__, __mul__
    def inverse(self): return pow(self.x, self.MOD - 2, self.MOD)

def main():
    N, M = LI()
    factinv = FactInv(M)
    a = ModInt(factinv.perm(M, N))
    tmp = ModInt(0)

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

    print(a * tmp)





if __name__ == '__main__':
    main()

Submission status: Accepted

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

def invmod(a):
  return pow(a,MOD-2,MOD)

fact_list=[1]
fact_inv_list=[1]
for i in range(1,M+1):
  fact_mod=(fact_list[-1]*i)%MOD
  fact_list.append(fact_mod)
  fact_inv_list.append(invmod(fact_mod))
def comb_mod_table(n,r):
  if 0<=r<=n:
    return fact_list[n]*fact_inv_list[r]*fact_inv_list[n-r]
  else:
    return 0
def perm_mod_table(n,r):
  if 0<=r<=n:
    return fact_list[n]*fact_inv_list[n-r]
  else:
    return 0
  
answer=0
for i in range(N+1):  
  term=comb_mod_table(N,i)*pow(-1,i)*perm_mod_table(M,i)*perm_mod_table(M-i,N-i)*perm_mod_table(M-i,N-i)
  answer=(answer+term)%MOD
  
print(answer)

Submission status: Accepted

Solution code:

def factorials_with_inv(k,mod):
    """
    0! ... k! とそれらのmod逆元を求めて返す
    """
    fac = [1]*(k+1)
    inv = [1]*(k+1)
    t = 1
    for i in range(1,k+1):
        t *= i
        t %= mod
        fac[i] = t

    t = pow(t,-1,mod)
    for i in reversed(range(1,k+1)):
        inv[i] = t
        t *= i
        t %= mod

    return fac, inv

MOD = 10**9+7

def solve(N,M):
    fac,inv = factorials_with_inv(max(N,M), MOD)

    # (M-k)!/(k!(N-k)!) * N!M!/((M-N)!^2)

    res = 0
    sign = True
    for k in range(N+1):
        t = fac[M-k]*inv[k]*inv[N-k]
        if sign:
            res += t
        else:
            res -= t
        res %= MOD
        sign = not sign

    res *= fac[N]*fac[M]*inv[M-N]**2
    res %= MOD
    return res

from itertools import permutations

def naive(N,M):
    res = 0
    for A in permutations(range(M),N):
        for B in permutations(range(M),N):
            res += all(a != b for a,b in zip(A,B))
    return res%MOD

if __name__ == '__main__':
    N,M = map(int,input().split())

    # print(naive(N,M))
    print(solve(N,M))

Submission status: Accepted

Solution code:
class Combination:
    def __init__(self, n_max=10**6, mod=10**9+7):
        # self._n_max = n_max
        self._fac, self._finv, self._inv = [0]*n_max, [0]*n_max, [0]*n_max
        self._fac[0], self._fac[1] = 1, 1
        self._finv[0], self._finv[1] = 1, 1
        self._inv[1] = 1
        self._mod = mod
        for i in range(2, n_max):
            self._fac[i] = self._fac[i - 1] * i % self._mod
            self._inv[i] = self._mod - self._inv[self._mod%i] * (self._mod // i) % self._mod
            self._finv[i] = self._finv[i - 1] * self._inv[i] % self._mod
    def com(self, n, r):
        if n < r: return 0
        if n < 0 or r < 0: return 0
        return self._fac[n] * (self._finv[r] * self._finv[n - r] % self._mod) % self._mod

    def perm(self,n,r):
        if n < r: return 0
        if n < 0 or r < 0: return 0
        return self._fac[n] * (self._finv[n-r] % self._mod) % self._mod


MOD = 10**9+7
comb = Combination(10**6, MOD)

pls = [-1]*(10**6)
n,m = map(int, input().split())
# ans = perm(m,n)
ans = 0
for i in range(1,n+1):
    i_com = comb.com(n,i)
    pattern = comb.perm(m-i,n-i)
    if i%2 == 1:
        ans += i_com*pattern
    else:
        ans -= i_com*pattern
    ans%=MOD

ans = comb.perm(m,n)-ans
ans%=MOD

ans *= comb.perm(m,n)
print(ans%MOD)

Submission status: Accepted

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

fact = [0 for _ in range(MAX)]
factinv = [0 for _ in range(MAX)]

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

factinv[MAX - 1] = pow(fact[MAX - 1], MOD - 2, MOD)
for k in range(MAX - 1, 0, -1):
    factinv[k - 1] = factinv[k]*k
    factinv[k - 1] %= MOD

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

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

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

ans = 0
for k in range(n + 1):
    tmp = nCk(n, k)*nPk(m, k)*nPk(m - k, n - k)*nPk(m - k, n - k) % MOD
    if not k % 2: ans += tmp
    else: ans -= tmp
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import math
MOD = 10 ** 9 + 7

fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

def init(n):
    for i in range(2, n + 1):
        fact.append((fact[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
        factinv.append((factinv[-1] * inv[-1]) % MOD)

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

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

N, M = map(int, input().split())
init(M)
ans = 0
for k in range(N + 1):
    if k % 2 == 0:
        ans += nCk(N, k) * nPk(M - k, N - k)
    else:
        ans -= nCk(N, k) * nPk(M - k, N - k)
    ans = (ans + MOD) % MOD
ans *= nPk(M, N)
ans %= MOD
print(ans)

Submission status: Accepted

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

num = 500010
fact = [1] * (num+1)
ifact = [1] * (num+1)

for i in range(1,num+1):
    fact[i] = (fact[i-1] * i) % MOD
ifact[-1] = pow(fact[-1],MOD-2,MOD)
for i in range(1,num+1)[::-1]:
    ifact[i-1] = (ifact[i] * i)% MOD

def nPr(n,r):
    if r > n:
        return 0
    return (fact[n] * ifact[n-r]) % MOD
def nCr(n,r):
    if r > n:
        return 0
    return (fact[n] * ifact[r] * ifact[n-r]) % MOD

ans = nPr(M,N) ** 2
sign = -1
for n in range(1,N+1):
    t = (nPr(M,n) * nCr(N,n) * (nPr(M-n,N-n) ** 2))
    ans += sign * t
    sign *= -1
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


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


def comb(n, r):
    global MOD, modFacts, invs
    return (modFacts[n] * invs[n - r] * invs[r]) % MOD


def perm(n, r):
    global MOD, modFacts, invs
    return (modFacts[n] * invs[n - r]) % MOD


N, M = map(int, input().split())
modFacts, invs = prepare(M)
ans = 0
flag = 1
for i in range(N + 1):
    a = comb(N, i)
    b = perm(M, i)
    c = pow(perm(M - i, N - i), 2, MOD)
    cnt = (a * b * c) % MOD
    ans = (ans + flag * cnt) % MOD
    flag *= -1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
mod = 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) % mod)
  inv.append((-inv[mod % i] * (mod // i)) % mod)
  factinv.append((factinv[-1] * inv[-1]) % mod)

ans = 0
for k in range(N+1):
  if k%2 == 0:
    ans = (ans+factinv[N-k]*factinv[k]%mod*fact[M-k]%mod)%mod
  else:
    ans = (ans-factinv[N-k]*factinv[k]%mod*fact[M-k]%mod)%mod
ans = ans*fact[N]%mod*fact[M]%mod*factinv[M-N]%mod*factinv[M-N]%mod
print(ans)

Submission status: Accepted

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

MOD = 10**9+7
def frac(limit):
    frac = [1]*limit
    for i in range(2,limit):
        frac[i] = i * frac[i-1]%MOD
    fraci = [None]*limit
    fraci[-1] = pow(frac[-1], MOD -2, MOD)
    for i in range(-2, -limit-1, -1):
        fraci[i] = fraci[i+1] * (limit + i + 1) % MOD
    return frac, fraci
frac, fraci = frac(1341398)
def comb(a, b):
    if not a >= b >= 0:
        return 0
    return frac[a]*fraci[b]*fraci[a-b]%MOD


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

ans = 0

for i in range(N+1):
    sign = -1 if i&1 else 1
    ans = (ans + sign*comb(M, i)*comb(N, i)*frac[i]*comb(M-i, N-i)**2*frac[N-i]**2)%MOD

print(ans)

Submission status: Accepted

Solution code:
def cmb(n, r, mod):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod

def p(n,r,mod):
    return fact[n]*factinv[n-r] % mod
mod = 10 ** 9 + 7
maxi = 5*10 ** 5  # N は必要分だけ用意する
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, maxi + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
list=[0 for i in range(5*10**5+1)]
mod=10**9+7
list[0]=1
for i in range(len(list)-1):
  list[i+1]=list[i]*(i+1)%mod
def c(m,n):
  a=list[m]*pow(list[m-n],mod-2,mod)*pow(list[n],mod-2,mod)
  return a
def p(m,n):
  a=list[m]*pow(list[m-n],mod-2,mod)
  return a
ans=pow(p(M,N),2)
g=pow(list[M-N],mod-2,mod)
g2=pow(g,2,mod)
nn=list[N]
mm=list[M]
nmg=nn*mm*g2%mod
for i in range(1,N+1):
  ans+=nmg*pow(list[N-i],mod-2,mod)*pow(list[i],mod-2,mod)*list[M-i]*(-1)**i
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
mod = 10**9+7

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

#N!をmodで割った余りを前計算(Mまで)
R = [1]*(M+1)
for i in range(2,M+1):
    R[i] = R[i-1]*i
    R[i] %= mod

ans = 0

for k in range(N+1):
    a = (-1)**k
    a *= R[N]*R[M]*R[M-k]
    a %= mod
    a *= pow(R[k],mod-2,mod)
    a *= pow(R[N-k],mod-2,mod)
    a %= mod
    a *= (pow(R[M-N],mod-2,mod))**2
    a %= mod
    ans += a

print(ans%mod)