# ifac
def ifac(n):
  product = 1
  for i in range(1, n+1):
    product *= i
  return product

import sys
sys.setrecursionlimit(10000)

# rfac
def rfac(n):
  if n == 0:
    return 1
  else:
    return n * rfac(n-1)

# perm
def perm(n, r):
  return ifac(n)//ifac(n-r)

# comb
def comb(n, r):
  return ifac(n) // (ifac(r)*ifac(n-r))

# fib
def fib(n):
  if n == 1 or n == 2:
    return 1
  else:
    return fib(n-1) + fib(n-2)


# mfib
fibd = {}
def mfib(n):
  if n in fibd:
    return fibd[n]
  elif n == 0:
    return 0
  elif n == 1:
    return 1
  else:
    sum = mfib(n-1) + mfib(n-2)
    fibd[n] = sum
    return sum

# pascal
def pascal(row, col):
  if col == 0:
    return 1
  elif row == col:
    return 1
  else:
    return pascal(row-1, col-1) + pascal(row-1, col)

# mpascal
pasd = {}
def mpascal(row, col):
  if (row, col) in pasd:
    return pasd[(row, col)]
  elif col == 0:
    return 1
  elif row == col:
    return 1
  else:
    sum = mpascal(row-1, col-1) + mpascal(row-1, col)
    pasd[(row, col)] = sum
    return sum