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

Solution code:
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
MOD = 10**9+7

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

kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]
 
gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]
 
def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

def re_factorial(n):
    if n < 2:
        return 1
    return (n * re_factorial(n-1) %MOD)

#print(re_factorial(10))
first = ( nCr(M,N)*re_factorial(N) )%MOD
#print(first)
#print(first)

Mon = [-1]*(N+1)
Mon[1] = 0
Mon[2] = 1
def Montmort(n):
    if Mon[n] != -1:
        return Mon[n]
    else:
        return ((n-1)*(Montmort(n-1)+Montmort(n-2)))%MOD

def fib_memo(n):
    memo = [-1]*(n+1)

    def _fib(n):
        if n == 1:
            return 0
        elif n == 2:
            return 1
        if memo[n] != -1:
            return memo[n]
        memo[n] = ((n-1) * (_fib(n-1) + _fib(n-2)))%MOD
        return memo[n]

    return _fib(n)
    
second = fib_memo(N)

p = 0
for i in range(N+1):
    if i <= K:
        p += nCr(N,i) * nCr(K,i) * kaijo_memo[i]
    else:
        break

second *= p

#print(second)
print(first*second%MOD)

Submission status: Runtime Error

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

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

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

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

Solution code:
n = int(input())
alst = list(map(int, input().split()))
if n == 2:
    if sum(alst) % 2 != 0:
        print(-1)
    elif alst[0] < alst[1]:
        print(-1)
    else:
        print((alst[0] - alst[1]) // 2)
    exit()

if alst.count(1) == n:
    if n % 2 == 0:
        print(0)
    else:
        print(-1)
    exit()
    
if alst.count(1) == n - 1:
    if n % 2 == 1:
        print(0)
    else:
        print(-1)
    exit()

xor = 0
for num in alst[2:]:
    xor ^= num
total = alst[0] + alst[1]
if xor > total:
    print(-1)
    exit()

diff = total - xor
if diff % 2 == 1:
    print(-1)
    exit()

if alst[0] == 1:
    if xor == alst[0] ^ alst[1]:
        print(0)
    else:
        print(-1)
    exit()
    
diff //= 2
total_bin = format(total, "b")
diff_bin = format(diff,"b")
xor_bin = format(xor,"b")
i = len(total_bin)
ans = 0
for j in range(i, 0, -1):
    if j <= len(diff_bin):
        if diff_bin[-j] == "1":
            ans += 2 ** (j - 1)
            continue
for j in range(i, 0, -1):
    if j <= len(diff_bin):
        if diff_bin[-j] == "1":
            continue
    if j <= len(xor_bin):
        if xor_bin[-j] == "0":
            continue    
    if ans + 2 ** (j - 1) < alst[0]:
        ans += 2 ** (j - 1)
if ans == 0 or ans >= alst[0]:
    print(-1)
else:
    print(alst[0] - ans)

Submission status: Runtime Error

Solution code:
def mpn(m, n):
  c = 1
  for i in range(m-n+1, m+1):
    c *= i
  return c

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

a = mpn(m, n)
answer = a*a/2

print(answer % const)

Submission status: Runtime Error

Solution code:
def mpn(m, n):
  c = 1
  for i in range(m-n+1, m+1):
    c *= i
  return c

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

a = mpn(m, n)
answer = a*a/2

print(answer & const)

Submission status: Runtime Error

Solution code:
N, M, K = (int(s) for s in input().rstrip().split())

A = [int(s) for s in input().rstrip().split()]
B = [int(s) for s in input().rstrip().split()]

i, j = (0, 0)
sum, count = (0, 0)

while sum < K:
  if (i < N) and (j < M):
    if A[i] <= B[j]:
      sum += A[i]
      i += 1
      count += 1
    else:
      sum += B[j]
      j += 1
      count += 1
  elif i < N:
    sum += A[i]
    i += 1
    count += 1
  elif j < M:
    sum += B[j]
    j += 1
    count += 1
  else:
    break

if sum > K:
  count -= 1

print(count)