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: Wrong Answer

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 k % 2: ans += tmp
    else: ans -= tmp
    ans %= MOD

print(ans)

Submission status: Wrong Answer

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] = fact[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 k % 2: ans += tmp
    else: ans -= tmp
    ans %= MOD

print(ans)

Submission status: Wrong Answer

Solution code:
from functools import reduce

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

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

Submission status: Wrong Answer

Solution code:
from scipy.special import perm
from scipy.special import comb

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

p = perm(m,n,exact=True)
mod = 10**9 + 7

d = [0]*n
d[0] += p
for i in range(1,n):
  d[i] += ((perm(m,n-i,exact=True)*(perm(m-n+i,i,exact=True)**2) - sum(d[:i]))*comb(n,i,exact=True)) % mod
  
print(d)

ans = (p**2 - sum(d[:n])) % mod
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin

N, M = [int(x) for x in stdin.readline().rstrip().split()]
mod = 10 ** 9 + 7

dp = [(1, 1)]

for i in range(1, N + 1):
    if i == 1:
        dp.append((M - 1, M - 2))
        continue
    p = dp[-2][1] * (i - 1)
    p %= mod

    dp.append((((dp[-1][0] - p) * (M - i) + p * (M - i + 1)) % mod, ((dp[-1][0] - p) * (M - i)) % mod))

# print(dp)
ans = dp[-1][0]
for i in range(M, M - N, -1):
    ans *= i
    ans %= mod

print(ans)

Submission status: Wrong Answer

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

    __repr__ = __str__

    def __add__(self, other):
        return(
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )

    def __sub__(self, other):
        return(
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    
    def __mul__(self, other):
        return(
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )

    def __truediv__(self, other):
        return(
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2,MOD))
        )

    def __pow__(self, other):
        return(
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )


    __radd__ = __add__

    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )
MAX = 1000005
fac = [1,1]
finv = [1,1]
inv = [0,1]
def COMinit():
    for i in range(2,MAX):
        fac.append((fac[-1] * i) % MOD)
        inv.append((-inv[MOD%i] * (MOD//i)) % MOD)
        finv.append((finv[-1] * inv[-1]) % MOD)

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

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

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

Submission status: Wrong Answer

Solution code:
def FACTORIAL(M):
    i = 1
    result = 1
    while True:
        result *= i
        if i >= M:
            break
        i+=1
    return result

def C(M, N):
    return int(P(M, N) / FACTORIAL(N))

def P(M, N):
    cumul = 1
    iter = 0

    while True:
        if iter >= N:
            break
        cumul = cumul*M
        M-=1
        iter+=1
    return cumul

def main():
    s = input().split()
    N = int(s[0])
    M = int(s[1])
    MOD = 1000000007
    x = P(M, N)

    equal_num = 0
    result = x * x

    i = 1
    while True:
        y = P(M-i-1, N-i) * C(N, i)
        result = result - x * y
        i += 1
        if i > N or i > M-1:
            break
    print(result % MOD)

main()

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
MOD=int(1e9+7)
ans=M
for i in range(1,N):
    ans*=(M-i)*1*(M-i)+(M-i)*(M-(i+1))*(M-(i+1))
    ans%=MOD
print(ans%MOD)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

Submission status: Wrong Answer

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


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


class ModInt:
    def __init__(self, a, dvsr=DVSR):
        self.dvsr = dvsr
        self.value = a % dvsr

    def __iadd__(self, b):
        self.value += b
        self.value %= self.dvsr

    def __isub__(self, b):
        self.value -= b
        self.value %= self.dvsr

    def __imul__(self, b):
        self.value *= b
        self.value %= self.dvsr

    def __ifloordiv__(self, b):
        self.value *= pow(b, self.dvsr - 2, self.dvsr)
        self.value %= self.dvsr

    def __str__(self):
        return str(self.value)


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


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


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


ALL = ModInt(NPR(M, N))
ALL *= ALL.value

PAT = ModInt(0)

Submission status: Wrong Answer

Solution code:
from scipy.special import perm, comb

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

A = perm(M, N, exact=True) % mod

B = 0
for i in range(N + 1):
    B += (-1) ** i * comb(N, i, exact=True) * perm(M - i, N - i, exact=True) % mod

print(A * B)

Submission status: Wrong Answer

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

mod = 10**9+7

ans = 0

fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

max_num = max(n,m)

for i in range(2, max_num + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)


def prm(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] % p

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

if n == m:
    for i in range(n+1):
        #print(cmb(n,i,mod),i)
        ans += cmb(n,i,mod)*fact[n]*fact[n-i]*(-1)**(i)
        #print(ans)
        ans %= mod
        #print(ans)
    print(ans)
else:
    for i in range(n+1):
        ans += cmb(n,i,mod)*prm(m,n,mod)*prm(m,n-i,mod)*(-1)**(i)
        ans %= mod
        #print(ans)
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from math import comb
#DEBUG = True
DEBUG = False
if DEBUG:
    f=open("202006_5th/E_input.txt")
else:
    f=sys.stdin
N,M=map(int,f.readline().split())
mod=(10**9)+7
print((comb(M,N)**2*N)%mod)
f.close()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
#階乗計算
def facto(x):
  sumf=1
  if x==0:
    sumf=1
  else:
    for i in range(x):
      k=i+1
      sumf*=k
  return sumf
n,m=map(int,input().split())
nf=facto(n)
mf=facto(m)
mnf=facto((m-n))
#n=mの時
def ko1(x):
  kosuu1=0
  for i in range(x+1):
    kf=facto(i)
    kosuu1+=int((nf/kf)*((-1)**i))
  kosuu1*=nf
  return kosuu1
#n<mの時
def ko2(x,y):
  kosuu2=0
  for i in range(x+1):
    kf=facto(i)
    mi=facto((y-i))
    ni=facto((x-i))
    kosuu2+=int((((-1)**i)*mi*nf)/(ni*mnf*kf))
  kosuu2*=int(mf/mnf)
  return kosuu2
if n==m:
  kosuu=int(ko1(n)/(10**9+1))
else:
  kosuu=int((ko2(n,m))%(10**9+1))
print(kosuu)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(5*(10**5)+10)
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

def pmt(n, r, p):
    return (fact[n]/fact[n-r])%p

p = 10 ** 9 + 7
N = 5*(10 ** 5) 
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
    
def q(n,m,p):
    if n==1:
        return m-1
    else:
        sub=pmt(m,n,p)-cmb(n,n,p)
        for i in range(1,n):
            sub-=cmb(n,i,p)*q(n-i,m-i,p)
        return sub
n,m = map(int,input().split())
print(int((pmt(m,n,p)*q(n,m,p))%p))

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
fac=[1]*505050
inv=[1]*505050
finv=[1]*505050
mod=1000000007
for i in range(1,500010):
  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 C(n,r):
  if n<0 or r<0 or n<r: return 0
  return fac[n]*inv[n-r]*inv[r]%mod

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

Submission status: Wrong Answer

Solution code:
import sys
import time
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 factrial_memo(n):
  fact = [1, 1]
  for i in range(2, n + 1):
    fact.append((fact[-1] * i) % mod)
  return fact

def permutation(n,r): #nPr
  return fact[n]*pow(fact[n-r],mod-2,mod)%mod
  
def combination(n,r): #nCr
  return permutation(n,r)*pow(fact[r],mod-2,mod)%mod

def homogeneous(n,r): #nHr
  return combination(n+r-1,r)%mod

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

N,M = IL()

fact = factrial_memo(10**6)

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

Submission status: Wrong Answer

Solution code:
SIZE=5*10**5+1; MOD=10**9+7 #998244353 #ここを変更する
 
SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
fac = [0]*SIZE  # fac[j] = j! mod MOD
finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
    inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD
 
def choose(n,r): # nCr mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0
 
def chofuku(n,r): # nHr mod MOD の計算
    return choose(n+r-1,r)

def narabekae(n,r): #nPr mod MOD の計算
    return fac[n]*finv[n-r]%MOD


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

Submission status: Wrong Answer

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

# A = M*(M-1)*(M-2)*...*(M-(N-1))
# B = ?

A = 1
for i in range(N):
    A *= (M-i)

B = int(M*(M-1)/2)

ans = A * B
ans = ans  % (10**9 + 7)
print(ans)

Submission status: Wrong Answer

Solution code:
from scipy.special import perm

Submission status: Wrong Answer

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

ans = M*(M-(N-2))

for i in range(1,N+1):
    ans *= ((M-i)**2) % (10**9 + 7)

print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a = 1
Mod=1e9+7
d = [1]*(n+1)
for i in range(n):
  d[i+1]=((m-n+i)*d[i]+i*d[i-1])%Mod
  a=a*(m-i)%Mod
print(int(a*d[n]%Mod))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(300000)
class BinomialCoefficient(object):

    def __init__(self, N=510000, MOD=10**9+7):
        self.fac = [1, 1]
        self.finv = [1, 1]
        self.inv = [0, 1]
        self.MOD = MOD
        for i in range(2, N + 1):
            self.fac.append((self.fac[-1] * i) % MOD)
            self.inv.append((-self.inv[MOD % i] * (MOD // i)) % MOD)
            self.finv.append((self.finv[-1] * self.inv[-1]) % MOD)

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

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


def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, M = MI()
bi = BinomialCoefficient()

ans = 0
for i in range(max(0, 2 * N - M), N + 1):
    sgn = (-1) ** i
    lans = bi.C(N, i) * bi.P(M - i, N - i) % MOD
    lans = lans * sgn
    ans = (ans + lans + MOD) % MOD

ans = ans * bi.P(M, N) % MOD
print(ans)

Submission status: Wrong Answer

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

dp = [0] * n
mod = 10**9 + 7


if n == 1:
    print((m-n) * m)
elif n == 2:
    ans = (m - n)**2 + (m - n + 1)
    for i in range(2):
        ans *= (m - i)
        ans %= mod
    print(ans)
else:
    dp[0] = m - n
    dp[1] = (m - n)**2 + (m - n + 1)


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

    ans = dp[-1]

    for i in range(n):
        ans *= (m - i)
        ans %= mod

    print(ans)

Submission status: Wrong Answer

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

dp = [0] * n
mod = 10**9 + 7


if n == 1:
    print(m-n)
elif n == 2:
    ans = (m - n)**2 + (m - n + 1)
    for i in range(2):
        ans *= (m - i)
        ans %= mod
    print(ans)
else:
    dp[0] = m - n
    dp[1] = (m - n)**2 + (m - n + 1)


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

    ans = dp[-1]

    for i in range(n):
        ans *= (m - i)
        ans %= mod

    print(ans)

Submission status: Wrong Answer

Solution code:
'''
完全順列(derangement)
モンモール数(Montmort number)
'''

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

# 片方の順列の総数を求める
ans = 1
for i in range(N):
    ans *= M-i
    ans %= MOD

# M枚からN枚選ぶ完全順列を計算
d2, d1 = 1, M-N
d0 = 1
for i in range(2, N+1):
    # 1がk番目にある
    # 1番目にkがある
    d0 = (i-1)*d2 % MOD
    # 1番目にkがない
    d0 += (M-N+i-1)*d1 % MOD
    d2, d1 = d1, d0

print(ans*d0 % MOD)

Submission status: Wrong Answer

Solution code:
from functools import reduce
mod = 10**9 + 7
n, m = map(int, input().split())
 
def comb(N, A, MOD):
    num = reduce(lambda x, y: x * y % MOD, range(N, N - A, -1))
    den = reduce(lambda x, y: x * y % MOD, range(1, A + 1))
    return num * pow(den, MOD - 2, MOD) % MOD
 
a = 1
for i in range(1, n+1):
    a *= i
    a %= mod
 
print((comb(m, n, mod) * comb(m, n, mod) - (a*comb(m, n, mod)%mod)%mod))

Submission status: Wrong Answer

Solution code:
MOD = 1000000007

COM_MAX = 10 ** 6

fac, finv, inv = [0] * (COM_MAX + 1), [0] * (COM_MAX + 1), [0] * (COM_MAX + 1)
fac[0] = fac[1] = finv[0] = finv[1] = inv[1] = 1

for i in range(2, COM_MAX + 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


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


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


def mod_com_once(n, r, MOD):
    if n < r or n < 0 or r < 0:
        return 0
    r = min(r, n - r)
    numer = denom = 1
    for i in range(n - r + 1, n + 1):
        numer = numer * i % MOD
    for i in range(1, r + 1):
        denom = denom * i % MOD
    return numer * pow(denom, MOD - 2, MOD) % MOD

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
#from heapq import heappop, heappush
#from collections import OrderedDict, defaultdict
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
from collections import deque
#import numba

def generate_inv(n,mod):
    """
    逆元行列
    n >= 2
    Note: mod must bwe a prime number
    """
    ret = [0, 1]
    for i in range(2,n+1):
        next = -ret[mod%i] * (mod // i)
        next %= mod
        ret.append(next)
    return ret

def generate_comb_m_i(M, inv, mod):
    ret = [1, M]
    for i in range(2, M+1):
        tmp = (ret[-1] * (M-(i-1)) * inv[i]) % mod
        ret.append(tmp)
    return ret
def generate_p_N_i(N, mod):
    ret = [1]
    for i in range(1, N+1):
        tmp = ret[-1] * (N - (i-1))
        tmp %= mod
        ret.append(tmp)
    return ret

def generate_p_mi_ni(M, N, mod):
    ret = deque([1])
    cache = deque([1])
    for i in range(1, N+1):
        tmp = (cache[0] * (M-N-i)) % mod
        cache.appendleft(tmp)
        ret.appendleft((tmp ** 2) % mod)
    return ret


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

    inv = generate_inv(M, mod)

    comb_m_i = generate_comb_m_i(M, inv, mod)
    #print(comb_m_i[0])
    p_N_i = generate_p_N_i(N, mod)
    #print(p_N_i[0])
    p_mi_ni = generate_p_mi_ni(M, N, mod)
    #print(p_mi_ni[0])

    ret = p_mi_ni[0]

    sub = 0
    for i in range(1, N+1):
        tmp = (comb_m_i[i] * p_N_i[i] * p_mi_ni[i]) % mod
        tmp *= (i%2) * 2 - 1
        tmp %= mod
        sub += tmp

    ret -= sub
    ret %= mod

    print(ret)

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
#from heapq import heappop, heappush
#from collections import OrderedDict, defaultdict
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
from collections import deque
#import numba

def generate_inv(n,mod):
    """
    逆元行列
    n >= 2
    Note: mod must bwe a prime number
    """
    ret = [0, 1]
    for i in range(2,n+1):
        next = -ret[mod%i] * (mod // i)
        next %= mod
        ret.append(next)
    return ret

def generate_comb_m_i(M, inv, mod):
    ret = [1, M]
    for i in range(2, M+1):
        tmp = ret[-1]
        tmp *= M-(i-1)
        tmp %= mod
        tmp *= inv[i]
        tmp %= mod
        ret.append(tmp)
    return ret
def generate_p_N_i(N, mod):
    ret = [1]
    for i in range(1, N+1):
        tmp = ret[-1] * (N - (i-1))
        tmp %= mod
        ret.append(tmp)
    return ret

def generate_p_mi_ni(M, N, mod):
    ret = deque([1])
    cache = deque([1])
    for i in range(1, N+1):
        tmp = cache[0]
        tmp *= M-N+i
        tmp %= mod
        cache.appendleft(tmp)
        ret.appendleft((tmp ** 2) % mod)
    return ret


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

    inv = generate_inv(M, mod)

    comb_m_i = generate_comb_m_i(M, inv, mod)
    print(comb_m_i[0])
    p_N_i = generate_p_N_i(N, mod)
    print(p_N_i[0])
    p_mi_ni = generate_p_mi_ni(M, N, mod)
    print(p_mi_ni[0])

    ret = p_mi_ni[0]

    sub = 0
    for i in range(1, N+1):
        tmp = comb_m_i[i]
        tmp *= p_N_i[i]
        tmp %= mod
        tmp *= p_mi_ni[i]
        tmp %= mod
        tmp *= (i%2) * 2 - 1
        tmp %= mod
        sub += tmp

    ret -= sub
    ret %= mod

    print(ret)




if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
def makefac(n):
    global faclist
    faclist = [1, 1]
    for i in range(2, n + 1):
        faclist.append(faclist[-1] * i % MOD)
    return None
def mcomb(n, r):#nCr % MOD
    return faclist[n] * pow(faclist[r], MOD - 2, MOD) * pow(faclist[n-r], -1) % MOD
def mperm(n, r):#nPr % MOD
    return faclist[n] * pow(faclist[n-r], MOD - 2, MOD)

N, M = map(int, input().split())
MOD = 10 ** 9 + 7
makefac(M)
ans = mperm(M, N)
for k in range(1, N + 1):
    ans += ((-1)**k * mcomb(N, k) * mperm(M - k, N - k)) % MOD
ans = ans * mperm(M, N) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
def makefac(n):
    global faclist
    faclist = [1, 1]
    for i in range(2, n + 1):
        faclist.append(faclist[-1] * i % MOD)
    return None
def mcomb(n, r):#nCr % MOD
    return (faclist[n] * pow(faclist[r],-1) % MOD) * pow(faclist[n-r], MOD - 2) % MOD
def mperm(n, r):#nPr % MOD
    return faclist[n] * pow(faclist[n-r],-1) % MOD

N, M = map(int, input().split())
MOD = 10 ** 9 + 7
makefac(M)
ans = mperm(M, N)
for k in range(1, N + 1):
    ans += ((-1)**k * mcomb(N, k) * mperm(M - k, N - k)) % MOD
ans = ans * mperm(M, N) % MOD
print(int(ans))

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7

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

seq = [0 for _ in range(N+1)]

seq[0] = 1
seq[1] = M-1

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

ans = seq[N]

# multiply answer by C(M, N)
cmn_den = 1
for i in range(1, N+1):
  cmn_den *= i
  cmn_den %= MOD

cmn_den = pow(cmn_den, MOD-2, MOD)
cmn_num = 1
for i in range(N):
  cmn_num *= M - i
  cmn_num %= MOD

cmn = (cmn_num * cmn_den) % MOD
ans *= cmn
ans %= MOD

print ans

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
mod = 1000000007

kai = [1 for _ in range(N+M+1)]
for i in range(2,N+M+1):
    kai[i] = (kai[i-1]*i)%mod
#%%
ap = 0
for i in range(1,N+1):
    sp = (kai[M]*pow(kai[M-i], mod-2, mod))%mod
    restp = (kai[M-i]*pow(kai[N-i], mod-2, mod))%mod
    chose = ((kai[N]*pow(kai[N-i], mod-2, mod))%mod*pow(kai[i], mod-2,mod))%mod
    sign = (-1)**i
    ap = (ap + (sign*sp)%mod*(chose*restp**2)%mod)%mod
    
answer = ((kai[M]*pow(kai[M-N], mod-2, mod))**2)%mod

#%%
print((answer + ap)%mod)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a,M,d=1,10**9+7,[1]*(n+1)
for i in range(n):
  d[i+1]=((m-n+1)*d[i]+i*d[i-1])%M
  a=a*(m-1)%M
print(a*d[-1]%M)

Submission status: Wrong Answer

Solution code:
"""
nCk := f[n] * g[n - k] * g[k](mod)
"""
def pre_c(n, mod):
    f = [0] * (n + 1)
    g = [0] * (n + 1)
    for i in range(n + 1):
        if i == 0:
            f[i] = 1
            g[i] = 1
        else:
            f[i] = (f[i - 1] * i) % mod
            g[i] = pow(f[i], mod - 2, mod)

    return f, g

n, m = map(int,input().split())
mod = 10 ** 9 + 7
f, g = pre_c(m, mod)
mCn = (f[m] * g[m - n] * g[n])

temp1 = (f[n] * f[n - 1])
temp2 = (f[n] * f[n])

if m < 2*n:
    res = (mCn ** 2 * temp1) %mod
else:
    m_nCn = (f[m - n] * g[n] * g[m - 2*n])
    execept = (mCn * m_nCn * temp2)
    res = (execept + ((mCn ** 2 - mCn * m_nCn) * temp1)) %mod
print(res)

Submission status: Wrong Answer

Solution code:
import sys
import math

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, M = [int(x) for x in input().split()]

    MOD = 10 ** 9 + 7

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

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

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

    X = fact[M] * factinv[M - N]

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

        ans %= MOD

    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7
MAXN = 5*(10**5)+5
fact = [1]
ifact = [1]
for i in range(MAXN):
    fact.append(fact[-1] * (i+1) % MOD)
    ifact.append(pow(fact[-1], MOD-2, MOD))
def nCr(n, r):
    return fact[n] * ifact[r] * ifact[n-r] % MOD

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

n, m = map(int, input().split())
ans = 0
for k in range(n+1):
    # tmp = pow(nPr(m-k, n-k), 2, MOD) * nPr(m, k) * nCr(n,k) % MOD
    # tmp = nPr(m-k, n-k) * nPr(m, n) * nCr(n,k) % MOD
    tmp = nPr(m-k, n-k) * nCr(n,k) % MOD
    if k%2:
        ans -= tmp
    else:
        ans += tmp
    ans *= nPr(m, n)
    ans %= MOD
ans = (ans + MOD) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
mod = pow(10, 9)+7
ans = 0
a = 1
b = 1
for i in range(n, m+1):
  b *= i
  b %= mod
for i in range(1, n+1):
  k = 1 if i%2 else -1
  ans += k*a*b**2
  ans %= mod
  a *= m-i
  a %= mod
  b *= pow(m-i, mod-2, mod)
  b %= mod
print(ans)