Problem:


Score : 500 points

Problem Statement

Count the pairs of length-N sequences consisting of integers between 1 and M (inclusive), A_1, A_2, \cdots, A_{N} and B_1, B_2, \cdots, B_{N}, that satisfy all of the following conditions:

A_i \neq B_i, for every i such that 1\leq i\leq N.

A_i \neq A_j and B_i \neq B_j, for every (i, j) such that 1\leq i < j\leq N.

Since the count can be enormous, print it modulo (10^9+7).

Constraints

1\leq N \leq M \leq 5\times10^5

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M

Output

Print the count modulo (10^9+7).

Sample Input 1

2 2

Sample Output 1

2

A_1=1,A_2=2,B_1=2,B_2=1 and A_1=2,A_2=1,B_1=1,B_2=2 satisfy the conditions.

Sample Input 2

2 3

Sample Output 2

18

Sample Input 3

141421 356237

Sample Output 3

881613484



Sample input:
2 2


Sample output:
2

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, M = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    def extgcd1(a0,b0):#計算量log(b0),フェルマーの小定理より早い
        u,v,a,b=1,0,a0,b0
        while b: t=a//b; a-=t*b; a,b=b,a; u,v=v,u-t*v
        if a!=1: return -1#互いに素じゃない
        return u%b0
    
    maxn=M
    fact=[1]*(maxn+1)#NはnCrの最大のn
    ifact=[1]*(maxn+1)
    x=1
    for i in range(2,maxn+1):
        x=(x*i)%mod
        fact[i]=x; ifact[i]=extgcd1(x,mod)
        
    def comb(n,r): return (fact[n]*ifact[r]%mod)*ifact[n-r]%mod
    def P(n,r): return (fact[n]*ifact[n-r]%mod)
    ans=0
    sin=-1
    for i in range(0,N+1):
        sin*=-1
        ans+=sin*comb(M,i)*P(N,i)%mod*(P(M-i,N-i)**2%mod)
        ans%=mod
        
        #print(ans)
    
    print(ans)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
mod = 10**9 + 7
n = 10**6

fact = [1]*(n+1)
rfact = [1]*(n+1)
r = 1
for i in range(1, n+1):
  fact[i] = r = r * i % mod
rfact[n] = r = pow(fact[n], mod-2, mod)
for i in range(n, 0, -1):
  rfact[i-1] = r = r * i % mod

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % mod

# nCk (mod MOD) を求める
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % mod

N,M = map(int, input().split())
a = perm(M,N)
b = 0
for i in range(N+1):
    if i % 2:
        b -= comb(N,i) * perm(M-i,N-i) % mod
    else:
        b += comb(N,i) * perm(M-i,N-i) % mod
b %= mod
ans = a * b % mod
print(ans)

Submission status: Accepted

Solution code:
MOD = (10 ** 9) + 7

fact = [0] * 1100000
invfact = [0] * 1100000

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

invfact[1100000 - 1] = pow(fact[1100000 - 1], MOD-2, MOD)

for i in range(1100000 - 1, 0, -1):
    invfact[i-1] = invfact[i] * i % MOD
    

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

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

## kokokara fine

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

print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

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

MOD = 10**9 + 7

def fact_table(N, MOD):
    inv = np.empty(N, np.int64)
    inv[0] = 0
    inv[1] = 1
    for n in range(2, N):
        q, r = divmod(MOD, n)
        inv[n] = inv[r] * (-q) % MOD
    fact = np.empty(N, np.int64)
    fact[0] = 1
    for n in range(1, N):
        fact[n] = n * fact[n - 1] % MOD
    fact_inv = np.empty(N, np.int64)
    fact_inv[0] = 1
    for n in range(1, N):
        fact_inv[n] = fact_inv[n - 1] * inv[n] % MOD
    return fact, fact_inv, inv

def main(N, M, MOD):
    fact, fact_inv, inv = fact_table(N + 1, MOD)
    x = fact[N] * fact_inv % MOD * fact_inv[::-1] % MOD
    x[1::2] *= (-1)
    x = x[::-1]
    p = 1  # M-N+1 * M-N+2 * ... *
    ret = 0
    for k in range(N + 1):
        ret += x[k] * p % MOD
        if k != N:
            p = p * (M - N + 1 + k) % MOD
    ret %= MOD
    return ret * p % MOD

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i8 = numba.int64
    cc = CC('my_module')

    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)

    fact_table = cc_export(fact_table, (i8, i8))
    main = cc_export(main, (i8, i8, i8))
    cc.compile()

from my_module import main

N, M = map(int, read().split())
print(main(N, M, MOD))

Submission status: Accepted

Solution code:
import sys

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
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 LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def nCr(com_n, com_r):
    if com_n < com_r: return 0
    return fac[com_n] * ifac[com_r] % md * ifac[com_n - com_r] % md

def nPr(com_n, com_r):
    if com_n < com_r: return 0
    return fac[com_n] * ifac[com_n - com_r] % md

md = 10 ** 9 + 7
n_max = 500005
fac = [1]
for i in range(1, n_max + 1): fac.append(fac[-1] * i % md)
ifac = [1] * (n_max + 1)
ifac[n_max] = pow(fac[n_max], md - 2, md)
for i in range(n_max - 1, 1, -1): ifac[i] = ifac[i + 1] * (i + 1) % md

def main():
    n,m=MI()
    ans=0
    for i in range(n+1):
        if i&1:ans-=nCr(n,i)*nPr(m,i)*nPr(m-i,n-i)**2
        else:ans+=nCr(n,i)*nPr(m,i)*nPr(m-i,n-i)**2
        ans%=md
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n,m=map(int,input().split())
mod=10**9+7
n_max=(10**6+1)
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
FI[n_max-1]=pow(F[n_max-1],mod-2,mod)
for i in reversed(range(n_max-1)):
  FI[i]=(FI[i+1]*(i+1))%mod
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%mod

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

Submission status: Accepted

Solution code:
SIZE=5*10**5; 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
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
    fac[i] = fac[i-1]*i%MOD
finv[-1] = pow(fac[-1],MOD-2,MOD)
for i in range(SIZE-1,0,-1):
    finv[i-1] = finv[i]*i%MOD
    inv[i] = finv[i]*fac[i-1]%MOD

def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0

def f(x,y):
    return fac[x]*finv[x-y]%MOD
    
    
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

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

ans = 0
r = 1
for u in range(n+1):
    ans += r*f(m-u,n-u)*choose(n,u)%MOD
    ans %= MOD
    r *= -1



print(ans*f(m,n)%MOD)

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    # comb init
    # mod = 1000000007
    nmax = 10 ** 6 + 10  # change here
    fac = [0] * nmax
    finv = [0] * nmax
    inv = [0] * nmax
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    for i in range(2, nmax):
        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, r):
        if n < r:
            return 0
        else:
            return (fac[n] * ((finv[r] * finv[n - r]) % mod)) % mod

    N, M = map(int, input().split())
    ans = 1
    for i in range(N):
        ans = (ans * (M-i))%mod
    ans = (ans * ans)%mod

    mpn = fac[M] * finv[M-N]
    for k in range(1, N+1):
        tmp = ((comb(N, k) * mpn)%mod * (fac[M-k] * finv[M-N])%mod)%mod
        ans = (ans + tmp * (-1)**k) % mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


n, m = map(int, input().split())
MOD = 10 ** 9 + 7
facts, finvs = prepare(m, MOD)
c = 1
ans = 0
base = facts[n] * facts[m] * finvs[m - n] * finvs[m - n] % MOD
for k in range(n + 1):
    tmp = base * facts[m - k] * finvs[k] * finvs[n - k] % MOD
    ans = (ans + c * tmp) % MOD
    c *= -1
print(ans)

Submission status: Accepted

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

mod = 10**9 + 7
l = 10**6
fac = [1]*l
facr = [1]*l

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

def combi(N,K):
    return fac[N]*facr[N-K]%mod*facr[K]%mod
def per(N,K):
    return fac[N]*facr[N-K]%mod

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

Submission status: Accepted

Solution code:
def cmb(n, r, mod):#コンビネーションの高速計算　
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 5*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

N,M=map(int,input().split())
ans=((g1[M]*g2[M-N]%mod)**2)%mod
#print(ans)
for i in range(1,N+1):
    ans+=(-1)**i*cmb(N,i,mod)*g1[M]*g2[M-i]*((g1[M-i]*g2[M-N])**2)
    #print((-1)**i*cmb(N,i,mod)*g1[M]*g2[M-i]*((g1[M-i]*g2[M-N])**2))
    ans%=mod

print(ans)

Submission status: Runtime Error

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

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: Runtime Error

Solution code:
%%writefile e.py
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def p(n, k, mod):
  x = 1
  for ik in range(k):
    x *= (n - ik)
    x %= mod
  return x

MAX = 10 ** 9 + 7
def main():
  n, m = map(int, input().strip().split())
  s = 0
  nck = 1
  mpk = 1
  mkpnk = p(m, n, MAX)
  for k in range(0, n+1):
    if 0 < k <= n:
      nck *= (n - (k-1)) * pow(k, MAX-2, MAX) 
      nck %= MAX
    if 0 < k <= m:
      mpk *= (m - (k-1))
      mpk %= MAX
    if 0 < k <= n:
      mkpnk *= pow(m - (k - 1), MAX-2, MAX) 
      mkpnk %= MAX
    s += nck * ( (-1) ** k) * mpk * (mkpnk) ** 2
    s %= MAX
  print(s)
  

if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007LL

vector<int64_t> mkprimes(int64_t N) {
  vector<int64_t> search;
  vector<int64_t> primes;
  for (int64_t i = 2; i <= N; i++) {
    search.push_back(i);
  }

  int64_t maxsize = (int64_t)sqrt(N + 1);
  while (true) {
    if (search.size() == 0LL) {
      break;
    }
    int64_t t = search[0];
    if (t > maxsize) {
      for (auto tt : search) {
        primes.push_back(tt);
      }
      break;
    }
    primes.push_back(t);
    vector<int64_t> new_search;

    for (int64_t i = 1; i < search.size(); i++) {
      if (search[i] % t != 0) {
        new_search.push_back(search[i]);
      }
    }
    search = new_search;
  }

  return primes;
}

int64_t P(int64_t M, int64_t N) {
  int64_t cumul = 1;
  int64_t iter = 0;
  for (int64_t i = M;; i--) {
    if (iter >= N) {
      break;
    }
    cumul = (cumul * i) % MOD;
    iter++;
  }
  return cumul;
}

vector<int64_t> prime_fact(int64_t M, vector<int64_t> &primes) {
  vector<int64_t> tbl;
  int64_t m = M;
  int64_t i = 0;
  while (m > 1) {
    while (m % primes[i] == 0) {
      m = m / primes[i];
      tbl.push_back(primes[i]);
    }
    i++;
  }
  return tbl;
}

int64_t C(int64_t M, int64_t N, vector<int64_t> &primes) {
  if (N > M / 2) {
    return C(M, M - N, primes);
  }

  unordered_map<int64_t, int64_t> upper_prime_facts;
  for (int64_t i = 0; i < N; i++) {
    for (auto p : prime_fact(M - i, primes)) {
      if (upper_prime_facts.count(p) == 0) {
        upper_prime_facts[p] = 0;
      }
      upper_prime_facts[p]++;
    }
  }
  for (int64_t i = 2; i <= N; i++) {
    for (auto p : prime_fact(i, primes)) {
      upper_prime_facts[p]--;
    }
  }

  int64_t cumul = 1;
  for (auto b : upper_prime_facts) {
    for (int64_t c = 0; c < b.second; c++) {
      cumul = (cumul * b.first) % MOD;
    }
  }
  return cumul;
}

int main() {
  int64_t N = 0;
  cin >> N;
  int64_t M = 0;
  cin >> M;

  // P(M,N) * ( P(M,N) - P(M-1,N-1)*N + P(M-2,N-2)*((N*(N-1))/2) )
  int64_t x = P(M, N);
  int64_t result = (x * x) % MOD;
  int64_t i = N;

  vector<int64_t> primes = mkprimes(M);
  while (i > 0) {
    int64_t y;
    if (i == N) {
      y = C(N, i, primes);
    } else if (i == M - 1) {
      y = 0;
    } else {
      y = (P(M - i - 1, N - i) * C(N, i, primes)) % MOD;
    }
    //   cout << M << " " << N << " " << i << " " << y << endl;
    result = result - (x * y) % MOD;
    if (result < 0) {
      result = MOD + result;
    }

    i -= 1;
  }

  cout << result << endl;
}

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10**7)
MOD=10**9+7
N, M = map(int, input().split())

@lru_cache(maxsize=None)
def fct(n, mod=MOD):
    return (n * fct(n-1)) % MOD if n != 0 else 1

@lru_cache(maxsize=None)
def pmu(n, r, mod=MOD):
    return (fct(n) * pow(fct(n-r), mod-2, mod)) % mod

@lru_cache(maxsize=None)
def cmb(n, r, mod=MOD):
    return (pmu(n, r) * pow(fct(r), mod-2, mod)) % mod

def solve():
    # {the num of case B when A=range(1,N+1)} x {permutation of A}
    # use inclusion-exclusion principle against former
    ans = 0
    for i in range(N+1):
        cp = cmb(N, i) * pmu(M-i, N-i)
        ans = (ans + (1 if i%2==0 else -1) * cp) % MOD
    return (ans * pmu(M, N)) % MOD

if __name__ == "__main__":
    print(solve())

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10**7)
MOD=10**9+7
N, M = map(int, input().split())

@lru_cache(maxsize=None)
def fct(n, mod=MOD):
    return (n * fct(n-1)) % MOD if n != 0 else 1

# @lru_cache(maxsize=None)
def pmu(n, r, mod=MOD):
    return (fct(n) * pow(fct(n-r), mod-2, mod)) % mod

# @lru_cache(maxsize=None)
def cmb(n, r, mod=MOD):
    return (pmu(n, r) * pow(fct(r), mod-2, mod)) % mod

def solve():
    # {the num of case B when A=range(1,N+1)} x {permutation of A}
    # use inclusion-exclusion principle against former
    ans = 0
    for i in range(N+1):
        cp = cmb(N, i) * pmu(M-i, N-i)
        ans = (ans + (1 if i%2==0 else -1) * cp) % MOD
    return (ans * pmu(M, N)) % MOD

if __name__ == "__main__":
    print(solve())

Submission status: Runtime Error

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
mod = 10**9+7 #出力の制限
N = 10**5 * 5 + 1
def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
def p(n,r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * 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 )
# a = cmb(n,r)
"""
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
"""

n,m = m()

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


dp[-1] *= p(m,n)
dp[-1] %= mod
print(dp[-1])

Submission status: Runtime Error

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
mod = 10**9+7 #出力の制限
N = 10**5 * 5 + 1
def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
def p(n,r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * 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 )
# a = cmb(n,r)
"""
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
"""

n,m = m()

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

dp[-1] *= p(m,n)
dp[-1] %= mod
print(dp[-1])

Submission status: Runtime Error

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i8 = numba.int64
    cc = CC('my_module')
 
    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)
 
    fact_table = cc_export(fact_table, (i8, i8))
    main = cc_export(main, (i8, i8, i8))
    cc.compile()

    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    n, m = map(int, input().split())

    #output
    mod = pow(10, 9) + 7

    n_ = 5 * pow(10, 5) + 5
    fun = [1] * (n_+1)
    for i in range(1, n_+1):
        fun[i] = fun[i-1] * i % mod
    rev = [1] * (n_+1)
    rev[n_] = pow(fun[n_], mod-2, mod)
    for i in range(n_-1, 0, -1):
        rev[i] = rev[i+1] * (i+1) % mod
    def cmb(n,r):
        if n < 0 or r < 0 or r > n: return 0
        return fun[n] * rev[r] % mod * rev[n-r] % mod
    def perm(n, r):
        if n < 0 or r < 0 or r > n: return 0
        return fun[n] * rev[n-r] % mod

    #Aを1, 2, ..., nとする。
    #求める写像の総数をs(n, m)とする。
    #s(n, m) = sum(k=0, n)(cmb(n, k)* (-1)^k * cmb(m-k, n-k)*(n-k)!)

    import math
    answer = 0
    for i in range(n+1):
        temp = perm(n, i) * cmb(m, i) * pow(perm(m-i, n-i), 2)
        temp %= mod
        if i % 2 == 0:
            answer += temp
        else:
            answer -= temp
    print(answer % mod)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    n, m = map(int, input().split())

    #output
    mod = pow(10, 9) + 7

    n_ = 4 * pow(10, 5) + 5
    fun = [1] * (n_+1)
    for i in range(1, n_+1):
        fun[i] = fun[i-1] * i % mod
    rev = [1] * (n_+1)
    rev[n_] = pow(fun[n_], mod-2, mod)
    for i in range(n_-1, 0, -1):
        rev[i] = rev[i+1] * (i+1) % mod
    def cmb(n,r):
        if n < 0 or r < 0 or r > n: return 0
        return fun[n] * rev[r] % mod * rev[n-r] % mod
    def perm(n, r):
        if n < 0 or r < 0 or r > n: return 0
        return fun[n] * rev[n-r] % mod

    #Aを1, 2, ..., nとする。
    #求める写像の総数をs(n, m)とする。
    #s(n, m) = sum(k=0, n)(cmb(n, k)* (-1)^k * cmb(m-k, n-k)*(n-k)!)

    import math
    answer = 0
    for i in range(n+1):
        temp = perm(n, i) * cmb(m, i) * pow(perm(m-i, n-i), 2)
        temp %= mod
        if i % 2 == 0:
            answer += temp
        else:
            answer -= temp
    print(answer % mod)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Submission status: Runtime Error

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), DVSR)
ALL *= ALL.value

PAT = ModInt(0)
for i in reversed(range(1, N+1)):
    v = ModInt(NCR(N, i), DVSR)
    v *= NPR(M, i)
    v *= NPR(M-i, N-i)
    v *= NPR(M-i, N-i)
    PAT = ModInt(v.value - PAT.value, DVSR)

print(ModInt(ALL.value - PAT.value, DVSR))

Submission status: Runtime Error

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)
for i in reversed(range(1, N+1)):
    v = ModInt(NCR(N, i))
    v *= NPR(M, i)
    v *= NPR(M-i, N-i)
    v *= NPR(M-i, N-i)
    PAT = ModInt(v.value - PAT.value)

Submission status: Runtime Error

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)
for i in reversed(range(1, N+1)):
    v = ModInt(NCR(N, i))
    v *= NPR(M, i)
    v *= NPR(M-i, N-i)
    v *= NPR(M-i, N-i)
    PAT = ModInt(v.value - PAT.value)

print(ModInt(ALL.value - PAT.value))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
#階乗計算
from math import factorial
n,m=map(int,input().split())
nf=factorial(n)
mf=factorial(m)
mnf=factorial((m-n))
#n=mの時
def ko1(x):
  kosuu1=0
  for i in range(x+1):
    kf=factorial(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=factorial(i)
    mi=factorial((y-i))
    ni=factorial((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: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,M = map(int,input().split())
fac = [1, 1]
inv = [0, 1]
finv = [1, 1]
MOD = 10**9+7
fac = [1, 1]
inv = [0, 1]
finv = [1, 1]
for i in range(2, M+1):
    fac.append(fac[-1] * i % MOD)
    inv.append(MOD - inv[MOD%i] * (MOD//i) % MOD)
    finv.append(finv[-1] * inv[-1] % MOD) 
def comb_mod(n, r, m):  #nCr mod m
    if (n<0 or r<0 or n<r): return 0
    r = min(r, n-r)
    return fac[n] * finv[n-r] * finv[r] % m

def chofuku(n,r): # nHr mod MOD の計算
    return comb_mod(n+r-1,r)
 
def narabekae(n,r,m): #nPr mod m の計算
    return fac[n]*finv[n-r]%m
ans = 0
for i in range(1,N+1):
    if i % 2 == 1:
        flag = 1
    else:
        flag = -1
    s = flag*comb_mod(N,i,MOD)*nPr(M-i,N-i,MOD)
    ans += s
    if ans > MOD:
        ans %= MOD
ans1 = 1
for i in range(N):
    ans1 *= (M-i)
    ans1 %= MOD
ans2 = (ans1*ans1)%MOD
ans3 = (ans*nPr(M,N,MOD)) %MOD
print((ans2-ans3)%MOD)

Submission status: Runtime Error

Solution code:
n = int(input())
ans = 0
for i in range(1,n+1):
    ans += (n//i)*(n//i + 1)/2*i
print(int(ans))