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:
from scipy.special import perm, comb

N = 510000
MAX_NUM = N + 1
MOD = pow(10, 9) + 7

fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]

fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1

for i in range(2,MAX_NUM):
    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 combinations(n,k):
    global fac, finv
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD

def main():
    N, M = map(int, input().split())
    allp = perm(M, N, exact=True)
    if N == M:
        print(allp)
        return
    tmpallp = allp
    for i in range(1, N):
        tmp = perm(M-i, N-i, exact=True)-1
        if i%2 == 1:
            tmpallp -= tmp*combinations(N, i)
        else:
            tmpallp += tmp*combinations(N, i)
    print((allp*(tmpallp-1))%MOD)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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 = 0
for i in range(N+1):
    temp = (d[N]*pow(d[N-i], P-2, P)*pow(max(i, 1), P-2, P))%P
    temp *= d[M]
    temp %= P
    temp *= pow(d[M-i], P-2, P)
    temp %= P
    temp *= ((d[M-i]*pow(max(M-N, 1), P-2, P))**2)%P
    ans += (temp%P)*(-1)**i
    ans %= P
print(ans%P)

Submission status: Wrong Answer

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

P = [i for i in range(M-N+1, M+1)]
for i in range(1, len(P)):
  P[i] *= P[i-1]
  P[i] %= 1000000007

C = [i for i in range(N//2, N+1)][::-1]
C = [1] + C
#print(C)
for i in range(2, len(C)):
  C[i] = C[i]*C[i-1]//i
  C[i] %= 1000000007

summ = [1 for _ in range(N)]
ans = [0 for _ in range(N)]

for i in range(N):
  num = N-i-1
  if num>N//2:
    num = N-num
  c = C[num]
  p = P[i]
  s = summ[i]
  a = (c*(p-s))%1000000007
  #print(c,p,s,a)
  ans[i] = a
  if i < N-1:
    summ[i+1] = a+summ[i]
 
print((ans[-1]*P[-1]%1000000007))

Submission status: Wrong Answer

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

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

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


ans = dp[n]

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

print(ans)

Submission status: Wrong Answer

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

MOD = 10**9+7

def main():
    N,M = map(int, readline().split())

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

    ans *= 2 * M - (2 * N - 1)
    ans %= MOD

    print(ans)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)
# mod comb
mod = 10**9 + 7
t = 500000
inv = [1] * (t+1)
fac = [1] * (t+1)
finv = [1] * (t+1)
inv[0] = 0


def inv_table():
    for i in range(2, t+1):
        inv[i] = inv[mod % i] * (mod - mod // i) % mod
        fac[i] = fac[i-1] * i % mod
        finv[i] = finv[i-1] * inv[i] % mod


def comb(n, r):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0

    return fac[n] * finv[r] % mod * finv[n-r] % mod


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


ans = [0] * (n+1)
@lru_cache(maxsize=10000000)
def f(x):
    if x == 1:
        return 0

    ret = 1
    for i in range(1, x):
        ret += comb(x, x-i) * f(i) % mod

    return fac[x] - ret


print(2 * f(n) * comb(m, n) % mod)

Submission status: Wrong Answer

Solution code:
import math

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

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

print(int(pow(permutations_count(M, N),2)//2)%(10**9+7))

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)%mod)

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)
# mod comb
mod = 10**9 + 7
t = 500000
inv = [1] * (t+1)
fac = [1] * (t+1)
finv = [1] * (t+1)
inv[0] = 0


def inv_table():
    for i in range(2, t+1):
        inv[i] = inv[mod % i] * (mod - mod // i) % mod
        fac[i] = fac[i-1] * i % mod
        finv[i] = finv[i-1] * inv[i] % mod


def comb(n, r):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0

    return fac[n] * finv[r] % mod * finv[n-r] % mod


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


@lru_cache(maxsize=10000000)
def f(x):
    if x == 1:
        return 0
    
    ret = 1
    for i in range(1, x):
        ret += comb(x, x-i) * f(i) % mod
    
    return fac[x] - ret
  
print(f(n) * comb(m, n) % mod)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
m = 5 * 10**5 + 500
fac = [0] * m
finv = [0] * m
inv = [0] * m


def COMBinitialize(m):
    fac[0] = 1
    finv[0] = 1
    if m > 1:
        fac[1] = 1
        finv[1] = 1
        inv[1] = 1
        for i in range(2, m):
            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 COMB(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD


COMBinitialize(m)


def main():
    N, M = (int(i) for i in input().split())
    if N == M == 1:
        return print(0)
    ans = 1
    for k in range(N):
        ans *= COMB(M, M-k-1) * 2
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def modconb(n,k,mod):
    # テーブルを作る
    fac = [0]*(n+1)
    finv = [0]*(n+1)
    inv = [0]*(n+1)  

    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

    for i in range(2,n+1):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod%i] * (mod//i) % mod
        finv[i] = finv[i-1] * inv[i] %mod
    # 計算
    if n<k: return 0
    if n<0 or k<0: return 0
    return(fac[n]*(finv[k]*finv[n-k]%mod)%mod),(fac[n]*finv[n-k])%mod

c,p = modconb(m,n,MOD)
print(p*(pow(m-1,n,MOD)-m+2)%MOD)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
mod=10**9+7
x=1
y=m
z=1
if n>m:
  print(0)
else:
  for i in range(n):
    x=(x*y)%mod
    y-=1
  for i in range(n):
    z=(z*(m-i-1))%mod+((((m-i))%mod**i)%mod)*i%mod
  ans=x*z%mod
  print(ans)

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)
temp1 = f[m] * g[m - n] * g[n] % mod
temp2 = f[n - 1]
ans = temp1 * (temp2%mod)
print(ans%mod)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate
from functools import reduce
from operator import xor, add


def read():
    N, M = map(int, input().strip().split())
    return N, M


def binom_preprocess(n, MOD=10**9+7):
    f = [0 for i in range(n+1)]  # n!
    invf = [0 for i in range(n+1)]  # (n!)^-1
    f[0] = 1
    f[1] = 1
    invf[0] = 1
    invf[1] = 1
    for i in range(2, n+1):
        f[i] = f[i-1] * i % MOD
        invf[i] = pow(f[i], MOD-2, MOD)
    return f, invf


def binom(n, k, f, invf, MOD=10**9+7):
    if n < k or n < 0 or k < 0:
        return 0
    else:
        return (f[n] * invf[k] % MOD) * invf[n-k] % MOD


def solve(N, M, p=10**9+7):
    dp = [0 for i in range(N+1)]
    dp[0] = N
    dp[1] = N-1
    #for i in range(2, N+1):
    #    dp[i] = dp[i-1] * (i-1) % p
    f, invf = binom_preprocess(M+1, MOD=p)
    base = binom(M, N, f, invf, MOD=p) * f[N]
    s = 0
    for k in range(0, N+1):
        u = binom(N, k, f, invf, MOD=p) * binom(M-N, N-k, f, invf, MOD=p) % p
        #u = dp[k] * binom(M-N, N-k, f, invf, MOD=p) % p
        s += u
    return base * s % p


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    N, M = [int(x) for x in input().strip().split()]
    fact = [1] * (M + 1)
    invfact = [1] * (M + 1)
    for i in range(2, M + 1):
        fact[i] = (fact[i] * i) % mod
    invfact = [1] * (M + 1)
    invfact[-1] = pow(fact[-1], mod-2, mod)
    for i in range(M-1, 0, -1):
        invfact[i] = (invfact[i+1] * (i+1)) % mod
    def nCr(n, r):
        r = min(r, n-r)
        if r == 0:
            return 1
        if r == 1:
            return n
        return ((fact[n] * invfact[r]) % mod) * invfact[n-r] % mod
    
    ans = (fact[M] * invfact[M-N]) % mod
    for i in range(N, max(1, N-(M-N)-1), -1):
        ans -= (nCr(N, i) * fact[M-i] * invfact[M-N]) % mod
    ans = (ans * (fact[M] * invfact[M-N])) % mod
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
list_M=[i*(i-1) for i in range(M+1)]
a_1 = list_M[M-N+1]
note = [None]*(N+2)
note[0]=0
note[1]=a_1
for i in range(2,N+2):
  note[i] = (i-1)*(note[i-1]+note[i-2])
print(note[N+1])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
mod=10**9+7
def permutation(n, x, mod=10**9+7):
    tmp = 1
    for i in range(n, n-x, -1):
        tmp = (tmp * i) % mod
    return tmp
def combination(n, x, mod=10**9+7):
    factorial = [1] * (n+1)
    t = 1
    for i in range(1, n+1):
        t = (t * i) % mod
        factorial[i] = t
    tmp = factorial[n]
    tmp = (tmp * pow(factorial[x], mod-2, mod)) % mod
    tmp = (tmp * pow(factorial[n-x], mod-2, mod)) % mod
    return tmp
l=min(m-n,n)
ans=0
for k in range(1,l+1):
  ans+=((combination(n,k)*permutation(n,k))%mod)*(permutation(n,n-k)-1)
  ans%=mod
if m>=2*n:
  ans=(ans+permutation(m,n)*(permutation(m-n,n)))%mod

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

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

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

dp = [0]*(N+1)

for i in range(1,N+1):
    if i == 1:
        dp[i] = M-N
    elif i == 2:
        dp[i] = 1
    else:
        dp[i] = (i-1)*dp[i-1]+(i-1)*dp[i-2]*(M-N)*dp[i-3]
        dp[i] %= mod

print((dp[N]*a) % mod)

Submission status: Wrong Answer

Solution code:
class comb():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD


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

a = 1
for i in range(N):
  a = a * (M - i) % MOD

P = [M - 1, ((M - 2) * (M - 2) + M - 1) % MOD]
for i in range(2, N):
  P.append((P[-1] + P[-2]) * (i) % MOD)

k = P[N - 1]
t = k
m = M - N

#Q = [1]
#for i in range(m, 0, -1):
#  Q.append(Q[-1] * i % MOD)

#com = comb(M + 1, MOD)
#for i in range(1, min(m + 1, N + 1)):
#  t = (t + k * com.com(N, i) * Q[i]) % MOD

ans = a * t % MOD

#print(Q)
print(ans)

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,M=MI()
    
    ###################################
    #0~Nまで逆元などを事前計算
    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

    fact=[1,1]
    factinv=[1,1]
    inv=[0,1]
    
    for i in range(2, max(N,M) + 3):
        fact.append((fact[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod // i)) % mod)
        factinv.append((factinv[-1] * inv[-1]) % mod)
    ###################################
    
    mon=[0]*(N+5)
    mon[1]=1
    mon[2]=2
    mon[3]=9
    for i in range(4,N+5):
        mon[i]=((i)*(mon[i-1]+mon[i-2]))%mod
        
    ans=0
    
    for i in range(M-N+1):
        #i個残りの要素で入れ替える
        c=cmb(N,i,mod)
        if c==0:
            break
        #残りの中からの選び方
        f=(fact[M-N]*factinv[M-N-i])%mod
        ans=(ans+c*f)%mod
        
    #Aの決め方&それに対するBの完全順列
    ans=(ans*mon[N]*fact[M]*factinv[M-N])%mod
    ans=(ans*pow(2,mod-2,mod))%mod
    print(ans)
    
    """
    N=3とかで違う，M=7とかで
    [1,2,3]の完全順列に
    [2,1,3]や[3,1,2]があるけど，これらから3つ入れ替えたものに
    両方[4,5,6]とかあってかぶって計算している
    
    """
    

    


    
    
        
    

main()

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
P = 10**9+7
factorial_N = 1
for i in range(2,N+1):
    factorial_N = factorial_N * i % P

#M_C_N
# mCn = 1
# for i in range(M-N+1,M+1):
#     mCn  = mCn * i % P
# for i in range(2,N+1):
#     mCn = mCn * pow(i,P-2,P) % P

#sum of nC1 .. nCn-1
sum_nCi = 0
tmp = 1
# for i in range(1,(N-1)//2+1):
for i in range(1,N):
    tmp = tmp * (N-i+1) % P
    tmp = tmp * pow(i,P-2,P) % P
    sum_nCi += tmp
# tmp *= 2
# if N % 2 == 0:
#     tmp = 
#mCn
mCn = 1
for i in range(1,N):
    mCn = mCn * (N-i+1) % P
    mCn = mCn * pow(i,P-2,P) % P
mPn = 1
for i in range(M-N+1,M+1):
    mPn = mPn * i % P
ans = mPn - sum_nCi % P
ans = ans * mCn % P
ans = ans * factorial_N % P
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
n,m=NM()
if n==1:
    print(m*(m-1))
    quit()
N=m
fac=[1]*(N+3)
inv=[1]*(N+3)
t=1
mod=10**9+7
for i in range(1,N+3):
    t*=i
    t%=mod
    fac[i]=t
t=pow(fac[N+2],mod-2,mod)
for i in range(N+2,0,-1):
    inv[i]=t
    t*=i
    t%=mod
def comb(n,r):
    if r>n or r<0:
        return 0
    return fac[n]*inv[n-r]*inv[r]%mod
dp=[0]*(n+1)
dp[0]=1
dp[1]=m-1
dp[2]=(m-2)*(m-1)
for i in range(2,n+1):
    dp[i]=(i-1)*dp[i-2]*(m-i+1)+(dp[i]-(i-1)*dp[i-2])*(m-i)
    dp[i]%=mod
ans=dp[n]*comb(m,n)*fac[n]%mod
print(ans)

Submission status: Wrong Answer

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

dp_A=[[0] for _ in range(N)]
dp_B=[[0] for _ in range(N)]
dp_A[0]=M
dp_B[0]=M*(M-1)%MOD

for i in range(1,N):
  dp_A[i]=(M-i)*dp_B[i-1]%MOD
  dp_B[i]=(M-i)*dp_B[i-1]+(M-i-1)*(dp_A[i]-dp_B[i-1])
  dp_B[i]%=MOD
  
#print(dp_A)
#print(dp_B)
print(dp_B[-1])

Submission status: Wrong Answer

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):
    if not a or not b:
        return 1
    comb = fac[a] * finv[b] % mod * finv[a - b] % mod
    return comb


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

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

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    N, M = [int(x) for x in input().strip().split()]
    fact = [1] * (M + 1)
    invfact = [1] * (M + 1)
    for i in range(2, M + 1):
        fact[i] = (fact[i] * i) % mod
    invfact = [1] * (M + 1)
    invfact[-1] = pow(fact[-1], mod-2, mod)
    for i in range(M-1, 0, -1):
        invfact[i] = (invfact[i+1] * (i+1)) % mod
    print(fact)
    print(invfact)
    def nCr(n, r):
        r = min(r, n-r)
        if r == 0:
            return 1
        if r == 1:
            return n
        return ((fact[n] * invfact[r]) % mod) * invfact[n-r] % mod
    
    ans = (fact[M] * invfact[M-N]) % mod
    print(ans)
    print(N, max(1, N-(M-N)-1))
    for i in range(N, max(1, N-(M-N)-1), -1):
        ans -= (nCr(N, i) * fact[M-i] * invfact[M-N]) % mod
    ans = (ans * (fact[M] * invfact[M-N])) % mod
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


def fractional(n):
    res = [0] * (n+1)
    res[0] = 1
    res[1] = 1
    for i in range(2, n+1):
        res[i] = res[i-1] * i
    return res


F = fractional(M+1)

ans = F[M] * pow(F[N], MOD-2, MOD) * pow(F[M-N], MOD-2, MOD) * F[N]
ans = (ans * ans) % MOD

b = F[M-1] * pow(F[M-1], MOD-2, MOD) * pow(F[M-1-(N-1)], MOD-2, MOD) * F[N-1]
b = (b*b) % MOD
b = (b * N) % MOD

ans -= b

if ans < 0:
    ans += MOD
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
import math
anss = 0
for i in range(abs(M - 2 * N), N + 1):
    d = math.factorial(i)
    for i in range(1, N - i + 1):
        d *= i
    anss += d
ans = 1
mod = 10 ** 9 + 7
for i in range(M, M - N, -1):
    ans *= i
    ans %= mod
ans = ans * anss
ans %= mod
print(ans)

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:
def choose(n,a,mod):
    x, y = 1, 1
    for i in range(a):
        x = x * (n - i) % mod
        y = y * (i + 1) % mod
    return x * pow(y, mod - 2, mod) % mod

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

Submission status: Wrong Answer

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

MOD = 10 ** 9 + 7
MAX = 500001
fac = [0] * (MAX+1)
finv = [0] * (MAX+1)
inv = [0] * (MAX+1)

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 ppp(nn, r):
    return fac[nn] * finv[nn - r] % MOD


a = int(ppp(m, n)) ** 2 % MOD

print(int(a/2))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret

    def perm(self, n, r):
        """
        nPrの値を返す
        """
        ret = self.f[n] * self.inv[n-r]
        ret %= self.mod
        return ret
N,M = map(int,input().split())
MOD=10**9+7

F=FactMod(M+1,MOD)


#DP[i]は長さiの完全順列の数
DP=[0]*(N+1)
DP[0]=0
DP[1]=0
if N>=2:
    DP[2]=1
    if N>=3:
        DP[3]=2
        for i in range(3,N+1):
            DP[i] = (i-1)*(DP[i-1]%MOD+DP[i-2]%MOD)%MOD
            DP[i]%=MOD

ans=0
A_pat=F.perm(M,N)

B_pat=[0]*(M-N+1) #B_pat[i]:1~N以外の数をiこつ使うときの通り数

B_pat[0]=DP[N]
for i in range(1,min(N+1,M-N+1)):
    #1~N以外の数を何個使うか
    #場所を選んで並べる
    B_pat[i] = F.comb(N,i)*F.perm(M-N+1-i,i)
    ans+=B_pat[i]
    B_pat[i]%=MOD


ans=0
for i in range(M-N+1):
    ans+=B_pat[i]
    ans%=MOD
ans*=A_pat
ans%=MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

mod = 10**9 + 7
def table(n:int, p=10**9+7):
    global fact, factinv, inv
    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 cmb(n:int, r:int, p=10**9+7):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

table(5 * (10**5))

N, M = mi()
ans = 0

if M >= N:
    for i in range(min(N+1, M-N+1)):
        ans += (cmb(N, i) * fact[M-N] / fact[max(M-N-i, 0)] * fact[N-1] / fact[max((N-1)-(N-i), 0)]) % mod
else:
    ans = 0

print(int((ans * fact[M])% mod))

Submission status: Wrong Answer

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

fac=[1]*(M+1)
for i in range(2,M+1):
    fac[i]=fac[i-1]*i%mod

inv=[1]*(M+1)
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 comb(n,r):
    if r>n or r<0:
        return 0
    ret=fac[n]*inv[r]*inv[n-r]%mod
    return ret

ans_A=comb(M,N)*fac[N]%mod
ans_B_0=fac[N]-1
ans_B=0
for i in range(1,M-N+1):
    ans_B+=ans_B_0*comb(N,i)%mod*comb(M-N,N-i)%mod
    ans_B%=mod
ans_B+=ans_B_0
print(ans_A*ans_B%mod)

Submission status: Wrong Answer

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

import sys
sys.setrecursionlimit(10000000)

N,M=nm()


def mod_permutation(n, k, mod):
        if n<=k:
            return 1
        else:
            return (n * mod_permutation(n-1,k,mod))%mod


def mod_combination(n, k, mod):
    # nCk (mod m)
    
    def mod_inv_permutation(k, mod):
        k, mod = int(k), int(mod)
        if k<=1:
            return 1
        else:
            return (pow(k,mod-2,mod) * mod_inv_permutation(k-1, mod))%mod

    return (mod_permutation(n,n-k,mod) * mod_inv_permutation(k, mod))%mod

MOD = 10**9+7
ans = mod_combination(M,N,MOD)*mod_permutation(M,N,MOD)%MOD
print(ans*2)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
dp=[0,0]
P=10**9+7

if (m==1):
    dp[0]=0
elif (m==2):
    dp[0]=2
else:
    dp[0]=m*(m-1)*(m-2)*(2*m-3)%P
    
if (n>2):
    for i in range(n-2):
        dp[1]=m*(m-1)*dp[0]%P
        dp[0]=dp[1]%P
elif (n==1):
    dp[1]=0
else:
    dp[1]=dp[0]
    
print(dp[1])

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

print((comb(m, n, mod) * comb(m, n, mod) - comb(m, n, mod)%mod))

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n,m=inpl()

class combination():
    def __init__(self, mod):
        '''
        modを指定して初期化
        '''
        self.mod = mod
        self.fac = [1, 1]  # 階乗テーブル
        self.ifac = [1, 1]  # 階乗の逆元テーブル
        self.inv = [0, 1]  # 逆元計算用

    def calc(self, n, k):
        '''
        nCk%modを計算する
        '''
        if k < 0 or n < k:
            return 0
        self.make_tables(n)  # テーブル作成
        k = min(k, n - k)
        return self.fac[n] * (self.ifac[k] * self.ifac[n - k] %
                              self.mod) % self.mod

    def make_tables(self, n):
        '''
        階乗テーブル・階乗の逆元テーブルを作成
        '''
        for i in range(len(self.fac), n + 1):
            self.fac.append((self.fac[-1] * i) % self.mod)
            self.inv.append(
                (-self.inv[self.mod % i] * (self.mod // i)) % self.mod)
            self.ifac.append((self.ifac[-1] * self.inv[-1]) % self.mod)


comb = combination(mod)
print(comb.calc(m-2,n)*(m-1))

Submission status: Wrong Answer

Solution code:
def nCr(n, r, mod):
    x, y = 1, 1
    for r_ in range(1, r+1):
        x = x*(n+1-r_)%mod
        y = y*r_%mod
    return x*pow(y, mod-2, mod)%mod

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

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

print((res//2)*res%mod)

Submission status: Wrong Answer

Solution code:
def main():
    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 5*(10**5)+1):
        fact.append(fact[-1]*i % mod)

    def nPr(n, r, mod=10**9+7):
        return pow(fact[n-r], mod-2, mod)*fact[n] % mod
    n, m = map(int, input().split())
    if m == 1:
        print(0)
        return
    ans = nPr(m, n)
    if m == n:
        print(ans)
        return
    if m-n == 1:
        a0 = 1
    else:
        a0 = 0
    a1 = 1
    for i in range((m-n-1), m-1):
        a1, a0 = ((i+1)*a1+(i-(m-n-1))*a0) % mod, a1
    print(a1*ans % mod)


main()

Submission status: Wrong Answer

Solution code:
def comb(n,k,mod):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    k=min(n-k,k)
    ans=1
    inv=[1]*(k+1)
    if k>=1:
        ans*=(n-k+1)%mod
    for i in range(2,k+1):
        inv[i]=mod-inv[mod%i]*(mod//i)%mod
        ans=ans*(n-k+i)*inv[i]%mod
    return ans

def perm(n, x, mod):
    tmp = 1
    for i in range(n, n-x, -1):
        tmp = (tmp * i) % mod
    return tmp

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

MOD = 10 ** 9 + 7

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

print(ans)

Submission status: Wrong Answer

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


def perm(m, n):
    ans = 1
    for i in range(m - n + 1, m + 1):
        ans *= i
        ans %= mod
    return ans


fac1 = [0] * (n + 1)
fac2 = [0] * (n + 1)
fac1[0] = m - n
fac2[0] = m - 1
for i in range(1, n):
    fac1[i] = fac1[i - 1] * (m - n - i) % mod
    fac2[i] = fac2[i - 1] * (m - i - 1) % mod
ans = 1
# print(fac1, fac2)
for i in range(n):
    ans = (ans + fac1[i] * fac2[n - i - 1]) % mod
print(perm(m, n) * ans % mod)

# print(perm(m, n), (perm(m - 1, n - 1), perm(m - 2, n - 1)))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret

    def perm(self, n, r):
        """
        nPrの値を返す
        """
        ret = self.f[n] * self.inv[n-r]
        ret %= self.mod
        return ret
N,M = map(int,input().split())
MOD=10**9+7

F=FactMod(M+1,MOD)


#DP[i]は長さiの完全順列の数
DP=[0]*(N+1)
DP[0]=0
DP[1]=0
if N>=2:
    DP[2]=1
    if N>=3:
        DP[3]=2
        for i in range(3,N+1):
            DP[i] = (i-1)*(DP[i-1]%MOD+DP[i-2]%MOD)%MOD
            DP[i]%=MOD

ans=0
A_pat=F.perm(M,N)

B_pat=[0]*(M-N+1) #B_pat[i]:1~N以外の数をiこつ使うときの通り数
B_pat[0]=DP[N]
for i in range(1,min(N+1,M-N+1)):
    #1~N以外の数を何個使うか
    #場所を選んで並べる
    B_pat[i] = F.comb(N,i)*F.fact(M-N+1-i)
    B_pat[i]%=MOD


ans=0
for i in range(M-N+1):
    ans+=B_pat[i]
    ans%=MOD
ans*=A_pat
ans%=MOD
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 5*(10**5)+1):
        fact.append(fact[-1]*i % mod)

    def nPr(n, r, mod=10**9+7):
        return pow(fact[n-r], mod-2, mod)*fact[n] % mod
    n, m = map(int, input().split())
    ans = nPr(m, n)
    if m == n:
        print(ans)
        return
    if m-n == 1:
        a0 = 1
    else:
        a0 = 0
    a1 = 1
    for i in range((m-n-1), m-1):
        a1, a0 = ((i+1)*a1+(i-(m-n-1))*a0) % mod, a1
    print(a1*ans % mod)


main()