Problem p02625 (python)

Fixed submission:
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())

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 nPr(n,r):
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

ans = 0
for i in range(N+1):
  ans += pow(-1,i,MOD) * nCr(N,i) * nPr(M,i) * ( nPr(M-i,N-i) )**2
  ans %= MOD
print(ans)

Buggy submission (verdict: Runtime Error):
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)