Coefficient du Binome


In [1]:
# temporairement je remprends la fonction de Sage
def binom(n, k):
    return binomial(n,k) #

In [2]:
[[binom(n, k) for k in range(n+1)] for n in range(10)]


Out[2]:
[[1],
 [1, 1],
 [1, 2, 1],
 [1, 3, 3, 1],
 [1, 4, 6, 4, 1],
 [1, 5, 10, 10, 5, 1],
 [1, 6, 15, 20, 15, 6, 1],
 [1, 7, 21, 35, 35, 21, 7, 1],
 [1, 8, 28, 56, 70, 56, 28, 8, 1],
 [1, 9, 36, 84, 126, 126, 84, 36, 9, 1]]

Chaines de bits de longueur n avec k 1


In [3]:
def list_BSnk(n, k):
    if k > n: 
        return []
    if k == 0:
        return [n*[0]]
    return ([[0]+x for x in list_BSnk(n-1, k)] +
            [[1]+x for x in list_BSnk(n-1, k-1)])

In [4]:
list_BSnk(5,2)


Out[4]:
[[0, 0, 0, 1, 1],
 [0, 0, 1, 0, 1],
 [0, 0, 1, 1, 0],
 [0, 1, 0, 0, 1],
 [0, 1, 0, 1, 0],
 [0, 1, 1, 0, 0],
 [1, 0, 0, 0, 1],
 [1, 0, 0, 1, 0],
 [1, 0, 1, 0, 0],
 [1, 1, 0, 0, 0]]

In [5]:
def rank_BSnk(x):
    if not x: return 0
    if x[0] == 0:           # liste vide
        return rank_BSnk(x[1:])
    else:
        return binom(len(x)-1, sum(x)-1) + rank_BSnk(x[1:])

def unrank_BSnk(n, k, i):
    if n == 0:
        return []
    bn1k = binom(n-1, k)
    if i < bn1k:
        return [0]+unrank_BSnk(n-1, k, i)
    else:
        return [1]+unrank_BSnk(n-1, k-1, i-bn1k)

In [6]:
rank_BSnk([0,1,0,1,0])


Out[6]:
4

In [7]:
list_BSnk(5,2)[4]


Out[7]:
[0, 1, 0, 1, 0]

In [8]:
unrank_BSnk(5,2,4)


Out[8]:
[0, 1, 0, 1, 0]

In [ ]:

Retour sur les coefficients du binome

Recursion, memoisation et programmation dynamique


In [9]:
def binom(n,k):
    if k > n:
        return 0
    if k == 0:
        return 1
    return binom(n-1, k) + binom(n-1, k-1)

In [10]:
[[binom(n, k) for k in range(n+1)] for n in range(10)]


Out[10]:
[[1],
 [1, 1],
 [1, 2, 1],
 [1, 3, 3, 1],
 [1, 4, 6, 4, 1],
 [1, 5, 10, 10, 5, 1],
 [1, 6, 15, 20, 15, 6, 1],
 [1, 7, 21, 35, 35, 21, 7, 1],
 [1, 8, 28, 56, 70, 56, 28, 8, 1],
 [1, 9, 36, 84, 126, 126, 84, 36, 9, 1]]

In [11]:
binom(100, 50) # tres long...


---------------------------------------------------------------------------
KeyboardInterrupt                         Traceback (most recent call last)
<ipython-input-11-c06ccdfb8416> in <module>()
----> 1 binom(Integer(100), Integer(50)) # tres long...

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

<ipython-input-9-b355864de08d> in binom(n, k)
      4     if k == Integer(0):
      5         return Integer(1)
----> 6     return binom(n-Integer(1), k) + binom(n-Integer(1), k-Integer(1))

src/cysignals/signals.pyx in cysignals.signals.python_check_interrupt (build/src/cysignals/signals.c:2854)()

src/cysignals/signals.pyx in cysignals.signals.sig_raise_exception (build/src/cysignals/signals.c:1303)()

KeyboardInterrupt: 

Memoization en utilisant les decorateurs de Python/Sage:


In [12]:
@cached_function
def binom(n, k):
    if k > n:
        return 0
    if k == 0:
        return 1
    return binom(n-1, k) + binom(n-1, k-1)

In [13]:
binom(100, 50)


Out[13]:
100891344545564193334812497256

Memoization a la main:


In [14]:
binomcache = {(0,0) : 1}

In [15]:
def binom(n, k):
    if k > n: return 0
    try:
        return binomcache[n,k]
    except KeyError:
        if k == 0: 
            res = 1
        else:
            res = binom(n-1, k) + binom(n-1, k-1)
        binomcache[n,k] = res
        return res

In [16]:
binom(100, 50)


Out[16]:
100891344545564193334812497256

In [17]:
binomcache


Out[17]:
{(0, 0): 1,
 (1, 0): 1,
 (1, 1): 1,
 (2, 0): 1,
 (2, 1): 2,
 (2, 2): 1,
 (3, 0): 1,
 (3, 1): 3,
 (3, 2): 3,
 (3, 3): 1,
 (4, 0): 1,
 (4, 1): 4,
 (4, 2): 6,
 (4, 3): 4,
 (4, 4): 1,
 (5, 0): 1,
 (5, 1): 5,
 (5, 2): 10,
 (5, 3): 10,
 (5, 4): 5,
 (5, 5): 1,
 (6, 0): 1,
 (6, 1): 6,
 (6, 2): 15,
 (6, 3): 20,
 (6, 4): 15,
 (6, 5): 6,
 (6, 6): 1,
 (7, 0): 1,
 (7, 1): 7,
 (7, 2): 21,
 (7, 3): 35,
 (7, 4): 35,
 (7, 5): 21,
 (7, 6): 7,
 (7, 7): 1,
 (8, 0): 1,
 (8, 1): 8,
 (8, 2): 28,
 (8, 3): 56,
 (8, 4): 70,
 (8, 5): 56,
 (8, 6): 28,
 (8, 7): 8,
 (8, 8): 1,
 (9, 0): 1,
 (9, 1): 9,
 (9, 2): 36,
 (9, 3): 84,
 (9, 4): 126,
 (9, 5): 126,
 (9, 6): 84,
 (9, 7): 36,
 (9, 8): 9,
 (9, 9): 1,
 (10, 0): 1,
 (10, 1): 10,
 (10, 2): 45,
 (10, 3): 120,
 (10, 4): 210,
 (10, 5): 252,
 (10, 6): 210,
 (10, 7): 120,
 (10, 8): 45,
 (10, 9): 10,
 (10, 10): 1,
 (11, 0): 1,
 (11, 1): 11,
 (11, 2): 55,
 (11, 3): 165,
 (11, 4): 330,
 (11, 5): 462,
 (11, 6): 462,
 (11, 7): 330,
 (11, 8): 165,
 (11, 9): 55,
 (11, 10): 11,
 (11, 11): 1,
 (12, 0): 1,
 (12, 1): 12,
 (12, 2): 66,
 (12, 3): 220,
 (12, 4): 495,
 (12, 5): 792,
 (12, 6): 924,
 (12, 7): 792,
 (12, 8): 495,
 (12, 9): 220,
 (12, 10): 66,
 (12, 11): 12,
 (12, 12): 1,
 (13, 0): 1,
 (13, 1): 13,
 (13, 2): 78,
 (13, 3): 286,
 (13, 4): 715,
 (13, 5): 1287,
 (13, 6): 1716,
 (13, 7): 1716,
 (13, 8): 1287,
 (13, 9): 715,
 (13, 10): 286,
 (13, 11): 78,
 (13, 12): 13,
 (13, 13): 1,
 (14, 0): 1,
 (14, 1): 14,
 (14, 2): 91,
 (14, 3): 364,
 (14, 4): 1001,
 (14, 5): 2002,
 (14, 6): 3003,
 (14, 7): 3432,
 (14, 8): 3003,
 (14, 9): 2002,
 (14, 10): 1001,
 (14, 11): 364,
 (14, 12): 91,
 (14, 13): 14,
 (14, 14): 1,
 (15, 0): 1,
 (15, 1): 15,
 (15, 2): 105,
 (15, 3): 455,
 (15, 4): 1365,
 (15, 5): 3003,
 (15, 6): 5005,
 (15, 7): 6435,
 (15, 8): 6435,
 (15, 9): 5005,
 (15, 10): 3003,
 (15, 11): 1365,
 (15, 12): 455,
 (15, 13): 105,
 (15, 14): 15,
 (15, 15): 1,
 (16, 0): 1,
 (16, 1): 16,
 (16, 2): 120,
 (16, 3): 560,
 (16, 4): 1820,
 (16, 5): 4368,
 (16, 6): 8008,
 (16, 7): 11440,
 (16, 8): 12870,
 (16, 9): 11440,
 (16, 10): 8008,
 (16, 11): 4368,
 (16, 12): 1820,
 (16, 13): 560,
 (16, 14): 120,
 (16, 15): 16,
 (16, 16): 1,
 (17, 0): 1,
 (17, 1): 17,
 (17, 2): 136,
 (17, 3): 680,
 (17, 4): 2380,
 (17, 5): 6188,
 (17, 6): 12376,
 (17, 7): 19448,
 (17, 8): 24310,
 (17, 9): 24310,
 (17, 10): 19448,
 (17, 11): 12376,
 (17, 12): 6188,
 (17, 13): 2380,
 (17, 14): 680,
 (17, 15): 136,
 (17, 16): 17,
 (17, 17): 1,
 (18, 0): 1,
 (18, 1): 18,
 (18, 2): 153,
 (18, 3): 816,
 (18, 4): 3060,
 (18, 5): 8568,
 (18, 6): 18564,
 (18, 7): 31824,
 (18, 8): 43758,
 (18, 9): 48620,
 (18, 10): 43758,
 (18, 11): 31824,
 (18, 12): 18564,
 (18, 13): 8568,
 (18, 14): 3060,
 (18, 15): 816,
 (18, 16): 153,
 (18, 17): 18,
 (18, 18): 1,
 (19, 0): 1,
 (19, 1): 19,
 (19, 2): 171,
 (19, 3): 969,
 (19, 4): 3876,
 (19, 5): 11628,
 (19, 6): 27132,
 (19, 7): 50388,
 (19, 8): 75582,
 (19, 9): 92378,
 (19, 10): 92378,
 (19, 11): 75582,
 (19, 12): 50388,
 (19, 13): 27132,
 (19, 14): 11628,
 (19, 15): 3876,
 (19, 16): 969,
 (19, 17): 171,
 (19, 18): 19,
 (19, 19): 1,
 (20, 0): 1,
 (20, 1): 20,
 (20, 2): 190,
 (20, 3): 1140,
 (20, 4): 4845,
 (20, 5): 15504,
 (20, 6): 38760,
 (20, 7): 77520,
 (20, 8): 125970,
 (20, 9): 167960,
 (20, 10): 184756,
 (20, 11): 167960,
 (20, 12): 125970,
 (20, 13): 77520,
 (20, 14): 38760,
 (20, 15): 15504,
 (20, 16): 4845,
 (20, 17): 1140,
 (20, 18): 190,
 (20, 19): 20,
 (20, 20): 1,
 (21, 0): 1,
 (21, 1): 21,
 (21, 2): 210,
 (21, 3): 1330,
 (21, 4): 5985,
 (21, 5): 20349,
 (21, 6): 54264,
 (21, 7): 116280,
 (21, 8): 203490,
 (21, 9): 293930,
 (21, 10): 352716,
 (21, 11): 352716,
 (21, 12): 293930,
 (21, 13): 203490,
 (21, 14): 116280,
 (21, 15): 54264,
 (21, 16): 20349,
 (21, 17): 5985,
 (21, 18): 1330,
 (21, 19): 210,
 (21, 20): 21,
 (21, 21): 1,
 (22, 0): 1,
 (22, 1): 22,
 (22, 2): 231,
 (22, 3): 1540,
 (22, 4): 7315,
 (22, 5): 26334,
 (22, 6): 74613,
 (22, 7): 170544,
 (22, 8): 319770,
 (22, 9): 497420,
 (22, 10): 646646,
 (22, 11): 705432,
 (22, 12): 646646,
 (22, 13): 497420,
 (22, 14): 319770,
 (22, 15): 170544,
 (22, 16): 74613,
 (22, 17): 26334,
 (22, 18): 7315,
 (22, 19): 1540,
 (22, 20): 231,
 (22, 21): 22,
 (22, 22): 1,
 (23, 0): 1,
 (23, 1): 23,
 (23, 2): 253,
 (23, 3): 1771,
 (23, 4): 8855,
 (23, 5): 33649,
 (23, 6): 100947,
 (23, 7): 245157,
 (23, 8): 490314,
 (23, 9): 817190,
 (23, 10): 1144066,
 (23, 11): 1352078,
 (23, 12): 1352078,
 (23, 13): 1144066,
 (23, 14): 817190,
 (23, 15): 490314,
 (23, 16): 245157,
 (23, 17): 100947,
 (23, 18): 33649,
 (23, 19): 8855,
 (23, 20): 1771,
 (23, 21): 253,
 (23, 22): 23,
 (23, 23): 1,
 (24, 0): 1,
 (24, 1): 24,
 (24, 2): 276,
 (24, 3): 2024,
 (24, 4): 10626,
 (24, 5): 42504,
 (24, 6): 134596,
 (24, 7): 346104,
 (24, 8): 735471,
 (24, 9): 1307504,
 (24, 10): 1961256,
 (24, 11): 2496144,
 (24, 12): 2704156,
 (24, 13): 2496144,
 (24, 14): 1961256,
 (24, 15): 1307504,
 (24, 16): 735471,
 (24, 17): 346104,
 (24, 18): 134596,
 (24, 19): 42504,
 (24, 20): 10626,
 (24, 21): 2024,
 (24, 22): 276,
 (24, 23): 24,
 (24, 24): 1,
 (25, 0): 1,
 (25, 1): 25,
 (25, 2): 300,
 (25, 3): 2300,
 (25, 4): 12650,
 (25, 5): 53130,
 (25, 6): 177100,
 (25, 7): 480700,
 (25, 8): 1081575,
 (25, 9): 2042975,
 (25, 10): 3268760,
 (25, 11): 4457400,
 (25, 12): 5200300,
 (25, 13): 5200300,
 (25, 14): 4457400,
 (25, 15): 3268760,
 (25, 16): 2042975,
 (25, 17): 1081575,
 (25, 18): 480700,
 (25, 19): 177100,
 (25, 20): 53130,
 (25, 21): 12650,
 (25, 22): 2300,
 (25, 23): 300,
 (25, 24): 25,
 (25, 25): 1,
 (26, 0): 1,
 (26, 1): 26,
 (26, 2): 325,
 (26, 3): 2600,
 (26, 4): 14950,
 (26, 5): 65780,
 (26, 6): 230230,
 (26, 7): 657800,
 (26, 8): 1562275,
 (26, 9): 3124550,
 (26, 10): 5311735,
 (26, 11): 7726160,
 (26, 12): 9657700,
 (26, 13): 10400600,
 (26, 14): 9657700,
 (26, 15): 7726160,
 (26, 16): 5311735,
 (26, 17): 3124550,
 (26, 18): 1562275,
 (26, 19): 657800,
 (26, 20): 230230,
 (26, 21): 65780,
 (26, 22): 14950,
 (26, 23): 2600,
 (26, 24): 325,
 (26, 25): 26,
 (26, 26): 1,
 (27, 0): 1,
 (27, 1): 27,
 (27, 2): 351,
 (27, 3): 2925,
 (27, 4): 17550,
 (27, 5): 80730,
 (27, 6): 296010,
 (27, 7): 888030,
 (27, 8): 2220075,
 (27, 9): 4686825,
 (27, 10): 8436285,
 (27, 11): 13037895,
 (27, 12): 17383860,
 (27, 13): 20058300,
 (27, 14): 20058300,
 (27, 15): 17383860,
 (27, 16): 13037895,
 (27, 17): 8436285,
 (27, 18): 4686825,
 (27, 19): 2220075,
 (27, 20): 888030,
 (27, 21): 296010,
 (27, 22): 80730,
 (27, 23): 17550,
 (27, 24): 2925,
 (27, 25): 351,
 (27, 26): 27,
 (27, 27): 1,
 (28, 0): 1,
 (28, 1): 28,
 (28, 2): 378,
 (28, 3): 3276,
 (28, 4): 20475,
 (28, 5): 98280,
 (28, 6): 376740,
 (28, 7): 1184040,
 (28, 8): 3108105,
 (28, 9): 6906900,
 (28, 10): 13123110,
 (28, 11): 21474180,
 (28, 12): 30421755,
 (28, 13): 37442160,
 (28, 14): 40116600,
 (28, 15): 37442160,
 (28, 16): 30421755,
 (28, 17): 21474180,
 (28, 18): 13123110,
 (28, 19): 6906900,
 (28, 20): 3108105,
 (28, 21): 1184040,
 (28, 22): 376740,
 (28, 23): 98280,
 (28, 24): 20475,
 (28, 25): 3276,
 (28, 26): 378,
 (28, 27): 28,
 (28, 28): 1,
 (29, 0): 1,
 (29, 1): 29,
 (29, 2): 406,
 (29, 3): 3654,
 (29, 4): 23751,
 (29, 5): 118755,
 (29, 6): 475020,
 (29, 7): 1560780,
 (29, 8): 4292145,
 (29, 9): 10015005,
 (29, 10): 20030010,
 (29, 11): 34597290,
 (29, 12): 51895935,
 (29, 13): 67863915,
 (29, 14): 77558760,
 (29, 15): 77558760,
 (29, 16): 67863915,
 (29, 17): 51895935,
 (29, 18): 34597290,
 (29, 19): 20030010,
 (29, 20): 10015005,
 (29, 21): 4292145,
 (29, 22): 1560780,
 (29, 23): 475020,
 (29, 24): 118755,
 (29, 25): 23751,
 (29, 26): 3654,
 (29, 27): 406,
 (29, 28): 29,
 (29, 29): 1,
 (30, 0): 1,
 (30, 1): 30,
 (30, 2): 435,
 (30, 3): 4060,
 (30, 4): 27405,
 (30, 5): 142506,
 (30, 6): 593775,
 (30, 7): 2035800,
 (30, 8): 5852925,
 (30, 9): 14307150,
 (30, 10): 30045015,
 (30, 11): 54627300,
 (30, 12): 86493225,
 (30, 13): 119759850,
 (30, 14): 145422675,
 (30, 15): 155117520,
 (30, 16): 145422675,
 (30, 17): 119759850,
 (30, 18): 86493225,
 (30, 19): 54627300,
 (30, 20): 30045015,
 (30, 21): 14307150,
 (30, 22): 5852925,
 (30, 23): 2035800,
 (30, 24): 593775,
 (30, 25): 142506,
 (30, 26): 27405,
 (30, 27): 4060,
 (30, 28): 435,
 (30, 29): 30,
 (30, 30): 1,
 (31, 0): 1,
 (31, 1): 31,
 (31, 2): 465,
 (31, 3): 4495,
 (31, 4): 31465,
 (31, 5): 169911,
 (31, 6): 736281,
 (31, 7): 2629575,
 (31, 8): 7888725,
 (31, 9): 20160075,
 (31, 10): 44352165,
 (31, 11): 84672315,
 (31, 12): 141120525,
 (31, 13): 206253075,
 (31, 14): 265182525,
 (31, 15): 300540195,
 (31, 16): 300540195,
 (31, 17): 265182525,
 (31, 18): 206253075,
 (31, 19): 141120525,
 (31, 20): 84672315,
 (31, 21): 44352165,
 (31, 22): 20160075,
 (31, 23): 7888725,
 (31, 24): 2629575,
 (31, 25): 736281,
 (31, 26): 169911,
 (31, 27): 31465,
 (31, 28): 4495,
 (31, 29): 465,
 (31, 30): 31,
 (31, 31): 1,
 (32, 0): 1,
 (32, 1): 32,
 (32, 2): 496,
 (32, 3): 4960,
 (32, 4): 35960,
 (32, 5): 201376,
 (32, 6): 906192,
 (32, 7): 3365856,
 (32, 8): 10518300,
 (32, 9): 28048800,
 (32, 10): 64512240,
 (32, 11): 129024480,
 (32, 12): 225792840,
 (32, 13): 347373600,
 (32, 14): 471435600,
 (32, 15): 565722720,
 (32, 16): 601080390,
 (32, 17): 565722720,
 (32, 18): 471435600,
 (32, 19): 347373600,
 (32, 20): 225792840,
 (32, 21): 129024480,
 (32, 22): 64512240,
 (32, 23): 28048800,
 (32, 24): 10518300,
 (32, 25): 3365856,
 (32, 26): 906192,
 (32, 27): 201376,
 (32, 28): 35960,
 (32, 29): 4960,
 (32, 30): 496,
 (32, 31): 32,
 (32, 32): 1,
 (33, 0): 1,
 (33, 1): 33,
 (33, 2): 528,
 (33, 3): 5456,
 (33, 4): 40920,
 (33, 5): 237336,
 (33, 6): 1107568,
 (33, 7): 4272048,
 (33, 8): 13884156,
 (33, 9): 38567100,
 (33, 10): 92561040,
 (33, 11): 193536720,
 (33, 12): 354817320,
 (33, 13): 573166440,
 (33, 14): 818809200,
 (33, 15): 1037158320,
 (33, 16): 1166803110,
 (33, 17): 1166803110,
 (33, 18): 1037158320,
 (33, 19): 818809200,
 (33, 20): 573166440,
 (33, 21): 354817320,
 (33, 22): 193536720,
 (33, 23): 92561040,
 (33, 24): 38567100,
 (33, 25): 13884156,
 (33, 26): 4272048,
 (33, 27): 1107568,
 (33, 28): 237336,
 (33, 29): 40920,
 (33, 30): 5456,
 (33, 31): 528,
 (33, 32): 33,
 (33, 33): 1,
 (34, 0): 1,
 (34, 1): 34,
 (34, 2): 561,
 (34, 3): 5984,
 (34, 4): 46376,
 (34, 5): 278256,
 (34, 6): 1344904,
 (34, 7): 5379616,
 (34, 8): 18156204,
 (34, 9): 52451256,
 (34, 10): 131128140,
 (34, 11): 286097760,
 (34, 12): 548354040,
 (34, 13): 927983760,
 (34, 14): 1391975640,
 (34, 15): 1855967520,
 (34, 16): 2203961430,
 (34, 17): 2333606220,
 (34, 18): 2203961430,
 (34, 19): 1855967520,
 (34, 20): 1391975640,
 (34, 21): 927983760,
 (34, 22): 548354040,
 (34, 23): 286097760,
 (34, 24): 131128140,
 (34, 25): 52451256,
 (34, 26): 18156204,
 (34, 27): 5379616,
 (34, 28): 1344904,
 (34, 29): 278256,
 (34, 30): 46376,
 (34, 31): 5984,
 (34, 32): 561,
 (34, 33): 34,
 (34, 34): 1,
 (35, 0): 1,
 (35, 1): 35,
 (35, 2): 595,
 (35, 3): 6545,
 (35, 4): 52360,
 (35, 5): 324632,
 (35, 6): 1623160,
 (35, 7): 6724520,
 (35, 8): 23535820,
 (35, 9): 70607460,
 (35, 10): 183579396,
 (35, 11): 417225900,
 (35, 12): 834451800,
 (35, 13): 1476337800,
 (35, 14): 2319959400,
 (35, 15): 3247943160,
 (35, 16): 4059928950,
 (35, 17): 4537567650,
 (35, 18): 4537567650,
 (35, 19): 4059928950,
 (35, 20): 3247943160,
 (35, 21): 2319959400,
 (35, 22): 1476337800,
 (35, 23): 834451800,
 (35, 24): 417225900,
 (35, 25): 183579396,
 (35, 26): 70607460,
 (35, 27): 23535820,
 (35, 28): 6724520,
 (35, 29): 1623160,
 (35, 30): 324632,
 (35, 31): 52360,
 (35, 32): 6545,
 (35, 33): 595,
 (35, 34): 35,
 (35, 35): 1,
 (36, 0): 1,
 (36, 1): 36,
 (36, 2): 630,
 (36, 3): 7140,
 (36, 4): 58905,
 (36, 5): 376992,
 (36, 6): 1947792,
 (36, 7): 8347680,
 (36, 8): 30260340,
 (36, 9): 94143280,
 (36, 10): 254186856,
 (36, 11): 600805296,
 (36, 12): 1251677700,
 (36, 13): 2310789600,
 (36, 14): 3796297200,
 (36, 15): 5567902560,
 (36, 16): 7307872110,
 (36, 17): 8597496600,
 (36, 18): 9075135300,
 (36, 19): 8597496600,
 (36, 20): 7307872110,
 (36, 21): 5567902560,
 (36, 22): 3796297200,
 (36, 23): 2310789600,
 (36, 24): 1251677700,
 (36, 25): 600805296,
 (36, 26): 254186856,
 (36, 27): 94143280,
 (36, 28): 30260340,
 (36, 29): 8347680,
 (36, 30): 1947792,
 (36, 31): 376992,
 (36, 32): 58905,
 (36, 33): 7140,
 (36, 34): 630,
 (36, 35): 36,
 (36, 36): 1,
 (37, 0): 1,
 (37, 1): 37,
 (37, 2): 666,
 (37, 3): 7770,
 (37, 4): 66045,
 (37, 5): 435897,
 (37, 6): 2324784,
 (37, 7): 10295472,
 (37, 8): 38608020,
 (37, 9): 124403620,
 (37, 10): 348330136,
 (37, 11): 854992152,
 (37, 12): 1852482996,
 (37, 13): 3562467300,
 (37, 14): 6107086800,
 (37, 15): 9364199760,
 (37, 16): 12875774670,
 (37, 17): 15905368710,
 (37, 18): 17672631900,
 (37, 19): 17672631900,
 (37, 20): 15905368710,
 (37, 21): 12875774670,
 (37, 22): 9364199760,
 (37, 23): 6107086800,
 (37, 24): 3562467300,
 (37, 25): 1852482996,
 (37, 26): 854992152,
 (37, 27): 348330136,
 (37, 28): 124403620,
 (37, 29): 38608020,
 (37, 30): 10295472,
 (37, 31): 2324784,
 (37, 32): 435897,
 (37, 33): 66045,
 (37, 34): 7770,
 (37, 35): 666,
 (37, 36): 37,
 (37, 37): 1,
 (38, 0): 1,
 (38, 1): 38,
 (38, 2): 703,
 (38, 3): 8436,
 (38, 4): 73815,
 (38, 5): 501942,
 (38, 6): 2760681,
 (38, 7): 12620256,
 (38, 8): 48903492,
 (38, 9): 163011640,
 (38, 10): 472733756,
 (38, 11): 1203322288,
 (38, 12): 2707475148,
 (38, 13): 5414950296,
 (38, 14): 9669554100,
 (38, 15): 15471286560,
 (38, 16): 22239974430,
 (38, 17): 28781143380,
 (38, 18): 33578000610,
 (38, 19): 35345263800,
 (38, 20): 33578000610,
 (38, 21): 28781143380,
 (38, 22): 22239974430,
 (38, 23): 15471286560,
 (38, 24): 9669554100,
 (38, 25): 5414950296,
 (38, 26): 2707475148,
 (38, 27): 1203322288,
 (38, 28): 472733756,
 (38, 29): 163011640,
 (38, 30): 48903492,
 (38, 31): 12620256,
 (38, 32): 2760681,
 (38, 33): 501942,
 (38, 34): 73815,
 (38, 35): 8436,
 (38, 36): 703,
 (38, 37): 38,
 (38, 38): 1,
 (39, 0): 1,
 (39, 1): 39,
 (39, 2): 741,
 (39, 3): 9139,
 (39, 4): 82251,
 (39, 5): 575757,
 (39, 6): 3262623,
 (39, 7): 15380937,
 (39, 8): 61523748,
 (39, 9): 211915132,
 (39, 10): 635745396,
 (39, 11): 1676056044,
 (39, 12): 3910797436,
 (39, 13): 8122425444,
 (39, 14): 15084504396,
 (39, 15): 25140840660,
 (39, 16): 37711260990,
 (39, 17): 51021117810,
 (39, 18): 62359143990,
 (39, 19): 68923264410,
 (39, 20): 68923264410,
 (39, 21): 62359143990,
 (39, 22): 51021117810,
 (39, 23): 37711260990,
 (39, 24): 25140840660,
 (39, 25): 15084504396,
 (39, 26): 8122425444,
 (39, 27): 3910797436,
 (39, 28): 1676056044,
 (39, 29): 635745396,
 (39, 30): 211915132,
 (39, 31): 61523748,
 (39, 32): 15380937,
 (39, 33): 3262623,
 (39, 34): 575757,
 (39, 35): 82251,
 (39, 36): 9139,
 (39, 37): 741,
 (39, 38): 39,
 (39, 39): 1,
 (40, 0): 1,
 (40, 1): 40,
 (40, 2): 780,
 (40, 3): 9880,
 (40, 4): 91390,
 (40, 5): 658008,
 (40, 6): 3838380,
 (40, 7): 18643560,
 (40, 8): 76904685,
 (40, 9): 273438880,
 (40, 10): 847660528,
 (40, 11): 2311801440,
 (40, 12): 5586853480,
 (40, 13): 12033222880,
 (40, 14): 23206929840,
 (40, 15): 40225345056,
 (40, 16): 62852101650,
 (40, 17): 88732378800,
 (40, 18): 113380261800,
 (40, 19): 131282408400,
 (40, 20): 137846528820,
 (40, 21): 131282408400,
 (40, 22): 113380261800,
 (40, 23): 88732378800,
 (40, 24): 62852101650,
 (40, 25): 40225345056,
 (40, 26): 23206929840,
 (40, 27): 12033222880,
 (40, 28): 5586853480,
 (40, 29): 2311801440,
 (40, 30): 847660528,
 (40, 31): 273438880,
 (40, 32): 76904685,
 (40, 33): 18643560,
 (40, 34): 3838380,
 (40, 35): 658008,
 (40, 36): 91390,
 (40, 37): 9880,
 (40, 38): 780,
 (40, 39): 40,
 (40, 40): 1,
 (41, 0): 1,
 (41, 1): 41,
 (41, 2): 820,
 (41, 3): 10660,
 (41, 4): 101270,
 (41, 5): 749398,
 (41, 6): 4496388,
 (41, 7): 22481940,
 (41, 8): 95548245,
 (41, 9): 350343565,
 (41, 10): 1121099408,
 (41, 11): 3159461968,
 (41, 12): 7898654920,
 (41, 13): 17620076360,
 (41, 14): 35240152720,
 (41, 15): 63432274896,
 (41, 16): 103077446706,
 (41, 17): 151584480450,
 (41, 18): 202112640600,
 (41, 19): 244662670200,
 (41, 20): 269128937220,
 (41, 21): 269128937220,
 (41, 22): 244662670200,
 (41, 23): 202112640600,
 (41, 24): 151584480450,
 (41, 25): 103077446706,
 (41, 26): 63432274896,
 (41, 27): 35240152720,
 (41, 28): 17620076360,
 (41, 29): 7898654920,
 (41, 30): 3159461968,
 (41, 31): 1121099408,
 (41, 32): 350343565,
 (41, 33): 95548245,
 (41, 34): 22481940,
 (41, 35): 4496388,
 (41, 36): 749398,
 (41, 37): 101270,
 (41, 38): 10660,
 (41, 39): 820,
 (41, 40): 41,
 (41, 41): 1,
 (42, 0): 1,
 (42, 1): 42,
 (42, 2): 861,
 (42, 3): 11480,
 (42, 4): 111930,
 (42, 5): 850668,
 (42, 6): 5245786,
 (42, 7): 26978328,
 (42, 8): 118030185,
 (42, 9): 445891810,
 (42, 10): 1471442973,
 (42, 11): 4280561376,
 (42, 12): 11058116888,
 (42, 13): 25518731280,
 (42, 14): 52860229080,
 (42, 15): 98672427616,
 (42, 16): 166509721602,
 (42, 17): 254661927156,
 (42, 18): 353697121050,
 (42, 19): 446775310800,
 (42, 20): 513791607420,
 (42, 21): 538257874440,
 (42, 22): 513791607420,
 (42, 23): 446775310800,
 (42, 24): 353697121050,
 (42, 25): 254661927156,
 (42, 26): 166509721602,
 (42, 27): 98672427616,
 (42, 28): 52860229080,
 (42, 29): 25518731280,
 (42, 30): 11058116888,
 (42, 31): 4280561376,
 (42, 32): 1471442973,
 (42, 33): 445891810,
 (42, 34): 118030185,
 (42, 35): 26978328,
 (42, 36): 5245786,
 (42, 37): 850668,
 (42, 38): 111930,
 (42, 39): 11480,
 (42, 40): 861,
 (42, 41): 42,
 (42, 42): 1,
 (43, 0): 1,
 (43, 1): 43,
 (43, 2): 903,
 (43, 3): 12341,
 (43, 4): 123410,
 (43, 5): 962598,
 (43, 6): 6096454,
 (43, 7): 32224114,
 (43, 8): 145008513,
 (43, 9): 563921995,
 (43, 10): 1917334783,
 (43, 11): 5752004349,
 (43, 12): 15338678264,
 (43, 13): 36576848168,
 (43, 14): 78378960360,
 (43, 15): 151532656696,
 (43, 16): 265182149218,
 (43, 17): 421171648758,
 (43, 18): 608359048206,
 (43, 19): 800472431850,
 (43, 20): 960566918220,
 (43, 21): 1052049481860,
 (43, 22): 1052049481860,
 (43, 23): 960566918220,
 (43, 24): 800472431850,
 (43, 25): 608359048206,
 (43, 26): 421171648758,
 (43, 27): 265182149218,
 (43, 28): 151532656696,
 (43, 29): 78378960360,
 (43, 30): 36576848168,
 (43, 31): 15338678264,
 (43, 32): 5752004349,
 (43, 33): 1917334783,
 (43, 34): 563921995,
 (43, 35): 145008513,
 (43, 36): 32224114,
 (43, 37): 6096454,
 (43, 38): 962598,
 (43, 39): 123410,
 (43, 40): 12341,
 (43, 41): 903,
 (43, 42): 43,
 (43, 43): 1,
 (44, 0): 1,
 (44, 1): 44,
 (44, 2): 946,
 (44, 3): 13244,
 (44, 4): 135751,
 (44, 5): 1086008,
 (44, 6): 7059052,
 (44, 7): 38320568,
 (44, 8): 177232627,
 (44, 9): 708930508,
 (44, 10): 2481256778,
 (44, 11): 7669339132,
 (44, 12): 21090682613,
 (44, 13): 51915526432,
 (44, 14): 114955808528,
 (44, 15): 229911617056,
 (44, 16): 416714805914,
 (44, 17): 686353797976,
 (44, 18): 1029530696964,
 (44, 19): 1408831480056,
 (44, 20): 1761039350070,
 (44, 21): 2012616400080,
 (44, 22): 2104098963720,
 (44, 23): 2012616400080,
 (44, 24): 1761039350070,
 (44, 25): 1408831480056,
 (44, 26): 1029530696964,
 (44, 27): 686353797976,
 (44, 28): 416714805914,
 (44, 29): 229911617056,
 (44, 30): 114955808528,
 (44, 31): 51915526432,
 (44, 32): 21090682613,
 (44, 33): 7669339132,
 (44, 34): 2481256778,
 (44, 35): 708930508,
 (44, 36): 177232627,
 (44, 37): 38320568,
 (44, 38): 7059052,
 (44, 39): 1086008,
 (44, 40): 135751,
 (44, 41): 13244,
 (44, 42): 946,
 (44, 43): 44,
 (44, 44): 1,
 (45, 0): 1,
 (45, 1): 45,
 (45, 2): 990,
 (45, 3): 14190,
 (45, 4): 148995,
 (45, 5): 1221759,
 (45, 6): 8145060,
 (45, 7): 45379620,
 (45, 8): 215553195,
 (45, 9): 886163135,
 (45, 10): 3190187286,
 (45, 11): 10150595910,
 (45, 12): 28760021745,
 (45, 13): 73006209045,
 (45, 14): 166871334960,
 (45, 15): 344867425584,
 (45, 16): 646626422970,
 (45, 17): 1103068603890,
 (45, 18): 1715884494940,
 (45, 19): 2438362177020,
 (45, 20): 3169870830126,
 (45, 21): 3773655750150,
 (45, 22): 4116715363800,
 (45, 23): 4116715363800,
 (45, 24): 3773655750150,
 (45, 25): 3169870830126,
 (45, 26): 2438362177020,
 (45, 27): 1715884494940,
 (45, 28): 1103068603890,
 (45, 29): 646626422970,
 (45, 30): 344867425584,
 (45, 31): 166871334960,
 (45, 32): 73006209045,
 (45, 33): 28760021745,
 (45, 34): 10150595910,
 (45, 35): 3190187286,
 (45, 36): 886163135,
 (45, 37): 215553195,
 (45, 38): 45379620,
 (45, 39): 8145060,
 (45, 40): 1221759,
 (45, 41): 148995,
 (45, 42): 14190,
 (45, 43): 990,
 (45, 44): 45,
 (45, 45): 1,
 (46, 0): 1,
 (46, 1): 46,
 (46, 2): 1035,
 (46, 3): 15180,
 (46, 4): 163185,
 (46, 5): 1370754,
 (46, 6): 9366819,
 (46, 7): 53524680,
 (46, 8): 260932815,
 (46, 9): 1101716330,
 (46, 10): 4076350421,
 (46, 11): 13340783196,
 (46, 12): 38910617655,
 (46, 13): 101766230790,
 (46, 14): 239877544005,
 (46, 15): 511738760544,
 (46, 16): 991493848554,
 (46, 17): 1749695026860,
 (46, 18): 2818953098830,
 (46, 19): 4154246671960,
 (46, 20): 5608233007146,
 (46, 21): 6943526580276,
 (46, 22): 7890371113950,
 (46, 23): 8233430727600,
 (46, 24): 7890371113950,
 (46, 25): 6943526580276,
 (46, 26): 5608233007146,
 (46, 27): 4154246671960,
 (46, 28): 2818953098830,
 (46, 29): 1749695026860,
 (46, 30): 991493848554,
 (46, 31): 511738760544,
 (46, 32): 239877544005,
 (46, 33): 101766230790,
 (46, 34): 38910617655,
 (46, 35): 13340783196,
 (46, 36): 4076350421,
 (46, 37): 1101716330,
 (46, 38): 260932815,
 (46, 39): 53524680,
 (46, 40): 9366819,
 (46, 41): 1370754,
 (46, 42): 163185,
 (46, 43): 15180,
 (46, 44): 1035,
 (46, 45): 46,
 (46, 46): 1,
 (47, 0): 1,
 (47, 1): 47,
 (47, 2): 1081,
 (47, 3): 16215,
 (47, 4): 178365,
 (47, 5): 1533939,
 (47, 6): 10737573,
 (47, 7): 62891499,
 (47, 8): 314457495,
 (47, 9): 1362649145,
 (47, 10): 5178066751,
 (47, 11): 17417133617,
 (47, 12): 52251400851,
 (47, 13): 140676848445,
 (47, 14): 341643774795,
 (47, 15): 751616304549,
 (47, 16): 1503232609098,
 (47, 17): 2741188875414,
 (47, 18): 4568648125690,
 (47, 19): 6973199770790,
 (47, 20): 9762479679106,
 (47, 21): 12551759587422,
 (47, 22): 14833897694226,
 (47, 23): 16123801841550,
 (47, 24): 16123801841550,
 (47, 25): 14833897694226,
 (47, 26): 12551759587422,
 (47, 27): 9762479679106,
 (47, 28): 6973199770790,
 (47, 29): 4568648125690,
 (47, 30): 2741188875414,
 (47, 31): 1503232609098,
 (47, 32): 751616304549,
 (47, 33): 341643774795,
 (47, 34): 140676848445,
 (47, 35): 52251400851,
 (47, 36): 17417133617,
 (47, 37): 5178066751,
 (47, 38): 1362649145,
 (47, 39): 314457495,
 (47, 40): 62891499,
 (47, 41): 10737573,
 (47, 42): 1533939,
 (47, 43): 178365,
 (47, 44): 16215,
 (47, 45): 1081,
 (47, 46): 47,
 (47, 47): 1,
 (48, 0): 1,
 (48, 1): 48,
 (48, 2): 1128,
 (48, 3): 17296,
 (48, 4): 194580,
 (48, 5): 1712304,
 (48, 6): 12271512,
 (48, 7): 73629072,
 (48, 8): 377348994,
 (48, 9): 1677106640,
 (48, 10): 6540715896,
 (48, 11): 22595200368,
 (48, 12): 69668534468,
 (48, 13): 192928249296,
 (48, 14): 482320623240,
 (48, 15): 1093260079344,
 (48, 16): 2254848913647,
 (48, 17): 4244421484512,
 (48, 18): 7309837001104,
 (48, 19): 11541847896480,
 (48, 20): 16735679449896,
 (48, 21): 22314239266528,
 (48, 22): 27385657281648,
 (48, 23): 30957699535776,
 (48, 24): 32247603683100,
 (48, 25): 30957699535776,
 (48, 26): 27385657281648,
 (48, 27): 22314239266528,
 (48, 28): 16735679449896,
 (48, 29): 11541847896480,
 (48, 30): 7309837001104,
 (48, 31): 4244421484512,
 (48, 32): 2254848913647,
 (48, 33): 1093260079344,
 (48, 34): 482320623240,
 (48, 35): 192928249296,
 (48, 36): 69668534468,
 (48, 37): 22595200368,
 (48, 38): 6540715896,
 (48, 39): 1677106640,
 (48, 40): 377348994,
 (48, 41): 73629072,
 (48, 42): 12271512,
 (48, 43): 1712304,
 (48, 44): 194580,
 (48, 45): 17296,
 (48, 46): 1128,
 (48, 47): 48,
 (48, 48): 1,
 (49, 0): 1,
 (49, 1): 49,
 (49, 2): 1176,
 (49, 3): 18424,
 (49, 4): 211876,
 (49, 5): 1906884,
 (49, 6): 13983816,
 (49, 7): 85900584,
 (49, 8): 450978066,
 (49, 9): 2054455634,
 (49, 10): 8217822536,
 (49, 11): 29135916264,
 (49, 12): 92263734836,
 (49, 13): 262596783764,
 (49, 14): 675248872536,
 (49, 15): 1575580702584,
 (49, 16): 3348108992991,
 (49, 17): 6499270398159,
 (49, 18): 11554258485616,
 (49, 19): 18851684897584,
 (49, 20): 28277527346376,
 (49, 21): 39049918716424,
 (49, 22): 49699896548176,
 (49, 23): 58343356817424,
 (49, 24): 63205303218876,
 (49, 25): 63205303218876,
 (49, 26): 58343356817424,
 (49, 27): 49699896548176,
 (49, 28): 39049918716424,
 (49, 29): 28277527346376,
 (49, 30): 18851684897584,
 (49, 31): 11554258485616,
 (49, 32): 6499270398159,
 (49, 33): 3348108992991,
 (49, 34): 1575580702584,
 (49, 35): 675248872536,
 (49, 36): 262596783764,
 (49, 37): 92263734836,
 (49, 38): 29135916264,
 (49, 39): 8217822536,
 (49, 40): 2054455634,
 (49, 41): 450978066,
 (49, 42): 85900584,
 (49, 43): 13983816,
 (49, 44): 1906884,
 (49, 45): 211876,
 (49, 46): 18424,
 (49, 47): 1176,
 (49, 48): 49,
 (49, 49): 1,
 (50, 0): 1,
 (50, 1): 50,
 (50, 2): 1225,
 (50, 3): 19600,
 (50, 4): 230300,
 (50, 5): 2118760,
 (50, 6): 15890700,
 (50, 7): 99884400,
 (50, 8): 536878650,
 (50, 9): 2505433700,
 (50, 10): 10272278170,
 (50, 11): 37353738800,
 (50, 12): 121399651100,
 (50, 13): 354860518600,
 (50, 14): 937845656300,
 (50, 15): 2250829575120,
 (50, 16): 4923689695575,
 (50, 17): 9847379391150,
 (50, 18): 18053528883775,
 (50, 19): 30405943383200,
 (50, 20): 47129212243960,
 (50, 21): 67327446062800,
 (50, 22): 88749815264600,
 (50, 23): 108043253365600,
 (50, 24): 121548660036300,
 (50, 25): 126410606437752,
 (50, 26): 121548660036300,
 (50, 27): 108043253365600,
 (50, 28): 88749815264600,
 (50, 29): 67327446062800,
 (50, 30): 47129212243960,
 (50, 31): 30405943383200,
 (50, 32): 18053528883775,
 (50, 33): 9847379391150,
 (50, 34): 4923689695575,
 (50, 35): 2250829575120,
 (50, 36): 937845656300,
 (50, 37): 354860518600,
 (50, 38): 121399651100,
 (50, 39): 37353738800,
 (50, 40): 10272278170,
 (50, 41): 2505433700,
 (50, 42): 536878650,
 (50, 43): 99884400,
 (50, 44): 15890700,
 (50, 45): 2118760,
 (50, 46): 230300,
 (50, 47): 19600,
 (50, 48): 1225,
 (50, 49): 50,
 (50, 50): 1,
 (51, 1): 51,
 (51, 2): 1275,
 (51, 3): 20825,
 (51, 4): 249900,
 (51, 5): 2349060,
 (51, 6): 18009460,
 (51, 7): 115775100,
 (51, 8): 636763050,
 (51, 9): 3042312350,
 (51, 10): 12777711870,
 (51, 11): 47626016970,
 (51, 12): 158753389900,
 (51, 13): 476260169700,
 (51, 14): 1292706174900,
 (51, 15): 3188675231420,
 (51, 16): 7174519270695,
 (51, 17): 14771069086725,
 (51, 18): 27900908274925,
 (51, 19): 48459472266975,
 (51, 20): 77535155627160,
 (51, 21): 114456658306760,
 (51, 22): 156077261327400,
 (51, 23): 196793068630200,
 (51, 24): 229591913401900,
 (51, 25): 247959266474052,
 (51, 26): 247959266474052,
 (51, 27): 229591913401900,
 (51, 28): 196793068630200,
 (51, 29): 156077261327400,
 (51, 30): 114456658306760,
 (51, 31): 77535155627160,
 (51, 32): 48459472266975,
 (51, 33): 27900908274925,
 (51, 34): 14771069086725,
 (51, 35): 7174519270695,
 (51, 36): 3188675231420,
 (51, 37): 1292706174900,
 (51, 38): 476260169700,
 (51, 39): 158753389900,
 (51, 40): 47626016970,
 (51, 41): 12777711870,
 (51, 42): 3042312350,
 (51, 43): 636763050,
 (51, 44): 115775100,
 (51, 45): 18009460,
 (51, 46): 2349060,
 (51, 47): 249900,
 (51, 48): 20825,
 (51, 49): 1275,
 (51, 50): 51,
 (52, 2): 1326,
 (52, 3): 22100,
 (52, 4): 270725,
 (52, 5): 2598960,
 (52, 6): 20358520,
 (52, 7): 133784560,
 (52, 8): 752538150,
 (52, 9): 3679075400,
 (52, 10): 15820024220,
 (52, 11): 60403728840,
 (52, 12): 206379406870,
 (52, 13): 635013559600,
 (52, 14): 1768966344600,
 (52, 15): 4481381406320,
 (52, 16): 10363194502115,
 (52, 17): 21945588357420,
 (52, 18): 42671977361650,
 (52, 19): 76360380541900,
 (52, 20): 125994627894135,
 (52, 21): 191991813933920,
 (52, 22): 270533919634160,
 (52, 23): 352870329957600,
 (52, 24): 426384982032100,
 (52, 25): 477551179875952,
 (52, 26): 495918532948104,
 (52, 27): 477551179875952,
 (52, 28): 426384982032100,
 (52, 29): 352870329957600,
 (52, 30): 270533919634160,
 (52, 31): 191991813933920,
 (52, 32): 125994627894135,
 (52, 33): 76360380541900,
 (52, 34): 42671977361650,
 (52, 35): 21945588357420,
 (52, 36): 10363194502115,
 (52, 37): 4481381406320,
 (52, 38): 1768966344600,
 (52, 39): 635013559600,
 (52, 40): 206379406870,
 (52, 41): 60403728840,
 (52, 42): 15820024220,
 (52, 43): 3679075400,
 (52, 44): 752538150,
 (52, 45): 133784560,
 (52, 46): 20358520,
 (52, 47): 2598960,
 (52, 48): 270725,
 (52, 49): 22100,
 (52, 50): 1326,
 (53, 3): 23426,
 (53, 4): 292825,
 (53, 5): 2869685,
 (53, 6): 22957480,
 (53, 7): 154143080,
 (53, 8): 886322710,
 (53, 9): 4431613550,
 (53, 10): 19499099620,
 (53, 11): 76223753060,
 (53, 12): 266783135710,
 (53, 13): 841392966470,
 (53, 14): 2403979904200,
 (53, 15): 6250347750920,
 (53, 16): 14844575908435,
 (53, 17): 32308782859535,
 (53, 18): 64617565719070,
 (53, 19): 119032357903550,
 (53, 20): 202355008436035,
 (53, 21): 317986441828055,
 (53, 22): 462525733568080,
 (53, 23): 623404249591760,
 (53, 24): 779255311989700,
 (53, 25): 903936161908052,
 (53, 26): 973469712824056,
 (53, 27): 973469712824056,
 (53, 28): 903936161908052,
 (53, 29): 779255311989700,
 (53, 30): 623404249591760,
 (53, 31): 462525733568080,
 (53, 32): 317986441828055,
 (53, 33): 202355008436035,
 (53, 34): 119032357903550,
 (53, 35): 64617565719070,
 (53, 36): 32308782859535,
 (53, 37): 14844575908435,
 (53, 38): 6250347750920,
 (53, 39): 2403979904200,
 (53, 40): 841392966470,
 (53, 41): 266783135710,
 (53, 42): 76223753060,
 (53, 43): 19499099620,
 (53, 44): 4431613550,
 (53, 45): 886322710,
 (53, 46): 154143080,
 (53, 47): 22957480,
 (53, 48): 2869685,
 (53, 49): 292825,
 (53, 50): 23426,
 (54, 4): 316251,
 (54, 5): 3162510,
 (54, 6): 25827165,
 (54, 7): 177100560,
 (54, 8): 1040465790,
 (54, 9): 5317936260,
 (54, 10): 23930713170,
 (54, 11): 95722852680,
 (54, 12): 343006888770,
 (54, 13): 1108176102180,
 (54, 14): 3245372870670,
 (54, 15): 8654327655120,
 (54, 16): 21094923659355,
 (54, 17): 47153358767970,
 (54, 18): 96926348578605,
 (54, 19): 183649923622620,
 (54, 20): 321387366339585,
 (54, 21): 520341450264090,
 (54, 22): 780512175396135,
 (54, 23): 1085929983159840,
 (54, 24): 1402659561581460,
 (54, 25): 1683191473897752,
 (54, 26): 1877405874732108,
 (54, 27): 1946939425648112,
 (54, 28): 1877405874732108,
 (54, 29): 1683191473897752,
 (54, 30): 1402659561581460,
 (54, 31): 1085929983159840,
 (54, 32): 780512175396135,
 (54, 33): 520341450264090,
 (54, 34): 321387366339585,
 (54, 35): 183649923622620,
 (54, 36): 96926348578605,
 (54, 37): 47153358767970,
 (54, 38): 21094923659355,
 (54, 39): 8654327655120,
 (54, 40): 3245372870670,
 (54, 41): 1108176102180,
 (54, 42): 343006888770,
 (54, 43): 95722852680,
 (54, 44): 23930713170,
 (54, 45): 5317936260,
 (54, 46): 1040465790,
 (54, 47): 177100560,
 (54, 48): 25827165,
 (54, 49): 3162510,
 (54, 50): 316251,
 (55, 5): 3478761,
 (55, 6): 28989675,
 (55, 7): 202927725,
 (55, 8): 1217566350,
 (55, 9): 6358402050,
 (55, 10): 29248649430,
 (55, 11): 119653565850,
 (55, 12): 438729741450,
 (55, 13): 1451182990950,
 (55, 14): 4353548972850,
 (55, 15): 11899700525790,
 (55, 16): 29749251314475,
 (55, 17): 68248282427325,
 (55, 18): 144079707346575,
 (55, 19): 280576272201225,
 (55, 20): 505037289962205,
 (55, 21): 841728816603675,
 (55, 22): 1300853625660225,
 (55, 23): 1866442158555975,
 (55, 24): 2488589544741300,
 (55, 25): 3085851035479212,
 (55, 26): 3560597348629860,
 (55, 27): 3824345300380220,
 (55, 28): 3824345300380220,
 (55, 29): 3560597348629860,
 (55, 30): 3085851035479212,
 (55, 31): 2488589544741300,
 (55, 32): 1866442158555975,
 (55, 33): 1300853625660225,
 (55, 34): 841728816603675,
 (55, 35): 505037289962205,
 (55, 36): 280576272201225,
 (55, 37): 144079707346575,
 (55, 38): 68248282427325,
 (55, 39): 29749251314475,
 (55, 40): 11899700525790,
 (55, 41): 4353548972850,
 (55, 42): 1451182990950,
 (55, 43): 438729741450,
 (55, 44): 119653565850,
 (55, 45): 29248649430,
 (55, 46): 6358402050,
 (55, 47): 1217566350,
 (55, 48): 202927725,
 (55, 49): 28989675,
 (55, 50): 3478761,
 (56, 6): 32468436,
 (56, 7): 231917400,
 (56, 8): 1420494075,
 (56, 9): 7575968400,
 (56, 10): 35607051480,
 (56, 11): 148902215280,
 (56, 12): 558383307300,
 (56, 13): 1889912732400,
 (56, 14): 5804731963800,
 (56, 15): 16253249498640,
 (56, 16): 41648951840265,
 (56, 17): 97997533741800,
 (56, 18): 212327989773900,
 (56, 19): 424655979547800,
 (56, 20): 785613562163430,
 (56, 21): 1346766106565880,
 (56, 22): 2142582442263900,
 (56, 23): 3167295784216200,
 (56, 24): 4355031703297275,
 (56, 25): 5574440580220512,
 (56, 26): 6646448384109072,
 (56, 27): 7384942649010080,
 (56, 28): 7648690600760440,
 (56, 29): 7384942649010080,
 (56, 30): 6646448384109072,
 (56, 31): 5574440580220512,
 (56, 32): 4355031703297275,
 (56, 33): 3167295784216200,
 (56, 34): 2142582442263900,
 (56, 35): 1346766106565880,
 (56, 36): 785613562163430,
 (56, 37): 424655979547800,
 (56, 38): 212327989773900,
 (56, 39): 97997533741800,
 (56, 40): 41648951840265,
 (56, 41): 16253249498640,
 (56, 42): 5804731963800,
 (56, 43): 1889912732400,
 (56, 44): 558383307300,
 (56, 45): 148902215280,
 (56, 46): 35607051480,
 (56, 47): 7575968400,
 (56, 48): 1420494075,
 (56, 49): 231917400,
 (56, 50): 32468436,
 (57, 7): 264385836,
 (57, 8): 1652411475,
 (57, 9): 8996462475,
 (57, 10): 43183019880,
 (57, 11): 184509266760,
 (57, 12): 707285522580,
 (57, 13): 2448296039700,
 (57, 14): 7694644696200,
 (57, 15): 22057981462440,
 (57, 16): 57902201338905,
 (57, 17): 139646485582065,
 (57, 18): 310325523515700,
 (57, 19): 636983969321700,
 (57, 20): 1210269541711230,
 (57, 21): 2132379668729310,
 (57, 22): 3489348548829780,
 (57, 23): 5309878226480100,
 (57, 24): 7522327487513475,
 (57, 25): 9929472283517787,
 (57, 26): 12220888964329584,
 (57, 27): 14031391033119152,
 (57, 28): 15033633249770520,
 (57, 29): 15033633249770520,
 (57, 30): 14031391033119152,
 (57, 31): 12220888964329584,
 (57, 32): 9929472283517787,
 (57, 33): 7522327487513475,
 (57, 34): 5309878226480100,
 (57, 35): 3489348548829780,
 (57, 36): 2132379668729310,
 (57, 37): 1210269541711230,
 (57, 38): 636983969321700,
 (57, 39): 310325523515700,
 (57, 40): 139646485582065,
 (57, 41): 57902201338905,
 (57, 42): 22057981462440,
 (57, 43): 7694644696200,
 (57, 44): 2448296039700,
 (57, 45): 707285522580,
 (57, 46): 184509266760,
 (57, 47): 43183019880,
 (57, 48): 8996462475,
 (57, 49): 1652411475,
 (57, 50): 264385836,
 (58, 8): 1916797311,
 (58, 9): 10648873950,
 (58, 10): 52179482355,
 (58, 11): 227692286640,
 (58, 12): 891794789340,
 (58, 13): 3155581562280,
 (58, 14): 10142940735900,
 (58, 15): 29752626158640,
 (58, 16): 79960182801345,
 (58, 17): 197548686920970,
 (58, 18): 449972009097765,
 (58, 19): 947309492837400,
 (58, 20): 1847253511032930,
 (58, 21): 3342649210440540,
 (58, 22): 5621728217559090,
 (58, 23): 8799226775309880,
 (58, 24): 12832205713993575,
 (58, 25): 17451799771031262,
 (58, 26): 22150361247847371,
 (58, 27): 26252279997448736,
 (58, 28): 29065024282889672,
 (58, 29): 30067266499541040,
 (58, 30): 29065024282889672,
 (58, 31): 26252279997448736,
 (58, 32): 22150361247847371,
 (58, 33): 17451799771031262,
 (58, 34): 12832205713993575,
 (58, 35): 8799226775309880,
 (58, 36): 5621728217559090,
 (58, 37): 3342649210440540,
 (58, 38): 1847253511032930,
 (58, 39): 947309492837400,
 (58, 40): 449972009097765,
 (58, 41): 197548686920970,
 (58, 42): 79960182801345,
 (58, 43): 29752626158640,
 (58, 44): 10142940735900,
 (58, 45): 3155581562280,
 (58, 46): 891794789340,
 (58, 47): 227692286640,
 (58, 48): 52179482355,
 (58, 49): 10648873950,
 (58, 50): 1916797311,
 (59, 9): 12565671261,
 (59, 10): 62828356305,
 (59, 11): 279871768995,
 (59, 12): 1119487075980,
 (59, 13): 4047376351620,
 (59, 14): 13298522298180,
 (59, 15): 39895566894540,
 (59, 16): 109712808959985,
 (59, 17): 277508869722315,
 (59, 18): 647520696018735,
 (59, 19): 1397281501935165,
 (59, 20): 2794563003870330,
 (59, 21): 5189902721473470,
 (59, 22): 8964377427999630,
 (59, 23): 14420954992868970,
 (59, 24): 21631432489303455,
 (59, 25): 30284005485024837,
 (59, 26): 39602161018878633,
 (59, 27): 48402641245296107,
 (59, 28): 55317304280338408,
 (59, 29): 59132290782430712,
 (59, 30): 59132290782430712,
 (59, 31): 55317304280338408,
 (59, 32): 48402641245296107,
 (59, 33): 39602161018878633,
 (59, 34): 30284005485024837,
 (59, 35): 21631432489303455,
 (59, 36): 14420954992868970,
 (59, 37): 8964377427999630,
 (59, 38): 5189902721473470,
 (59, 39): 2794563003870330,
 (59, 40): 1397281501935165,
 (59, 41): 647520696018735,
 (59, 42): 277508869722315,
 (59, 43): 109712808959985,
 (59, 44): 39895566894540,
 (59, 45): 13298522298180,
 (59, 46): 4047376351620,
 (59, 47): 1119487075980,
 (59, 48): 279871768995,
 (59, 49): 62828356305,
 (59, 50): 12565671261,
 (60, 10): 75394027566,
 (60, 11): 342700125300,
 (60, 12): 1399358844975,
 (60, 13): 5166863427600,
 (60, 14): 17345898649800,
 (60, 15): 53194089192720,
 (60, 16): 149608375854525,
 (60, 17): 387221678682300,
 (60, 18): 925029565741050,
 (60, 19): 2044802197953900,
 (60, 20): 4191844505805495,
 (60, 21): 7984465725343800,
 (60, 22): 14154280149473100,
 (60, 23): 23385332420868600,
 (60, 24): 36052387482172425,
 (60, 25): 51915437974328292,
 (60, 26): 69886166503903470,
 (60, 27): 88004802264174740,
 (60, 28): 103719945525634515,
 (60, 29): 114449595062769120,
 (60, 30): 118264581564861424,
 (60, 31): 114449595062769120,
 (60, 32): 103719945525634515,
 (60, 33): 88004802264174740,
 (60, 34): 69886166503903470,
 (60, 35): 51915437974328292,
 (60, 36): 36052387482172425,
 (60, 37): 23385332420868600,
 (60, 38): 14154280149473100,
 (60, 39): 7984465725343800,
 (60, 40): 4191844505805495,
 (60, 41): 2044802197953900,
 (60, 42): 925029565741050,
 (60, 43): 387221678682300,
 (60, 44): 149608375854525,
 (60, 45): 53194089192720,
 (60, 46): 17345898649800,
 (60, 47): 5166863427600,
 (60, 48): 1399358844975,
 (60, 49): 342700125300,
 (60, 50): 75394027566,
 (61, 11): 418094152866,
 (61, 12): 1742058970275,
 (61, 13): 6566222272575,
 (61, 14): 22512762077400,
 (61, 15): 70539987842520,
 (61, 16): 202802465047245,
 (61, 17): 536830054536825,
 (61, 18): 1312251244423350,
 (61, 19): 2969831763694950,
 (61, 20): 6236646703759395,
 (61, 21): 12176310231149295,
 (61, 22): 22138745874816900,
 (61, 23): 37539612570341700,
 (61, 24): 59437719903041025,
 (61, 25): 87967825456500717,
 (61, 26): 121801604478231762,
 (61, 27): 157890968768078210,
 (61, 28): 191724747789809255,
 (61, 29): 218169540588403635,
 (61, 30): 232714176627630544,
 (61, 31): 232714176627630544,
 (61, 32): 218169540588403635,
 (61, 33): 191724747789809255,
 (61, 34): 157890968768078210,
 (61, 35): 121801604478231762,
 (61, 36): 87967825456500717,
 (61, 37): 59437719903041025,
 (61, 38): 37539612570341700,
 (61, 39): 22138745874816900,
 (61, 40): 12176310231149295,
 (61, 41): 6236646703759395,
 (61, 42): 2969831763694950,
 (61, 43): 1312251244423350,
 (61, 44): 536830054536825,
 (61, 45): 202802465047245,
 (61, 46): 70539987842520,
 (61, 47): 22512762077400,
 (61, 48): 6566222272575,
 (61, 49): 1742058970275,
 (61, 50): 418094152866,
 (62, 12): 2160153123141,
 (62, 13): 8308281242850,
 (62, 14): 29078984349975,
 (62, 15): 93052749919920,
 (62, 16): 273342452889765,
 (62, 17): 739632519584070,
 (62, 18): 1849081298960175,
 (62, 19): 4282083008118300,
 (62, 20): 9206478467454345,
 (62, 21): 18412956934908690,
 (62, 22): 34315056105966195,
 (62, 23): 59678358445158600,
 (62, 24): 96977332473382725,
 (62, 25): 147405545359541742,
 (62, 26): 209769429934732479,
 (62, 27): 279692573246309972,
 (62, 28): 349615716557887465,
 (62, 29): 409894288378212890,
 (62, 30): 450883717216034179,
 (62, 31): 465428353255261088,
 (62, 32): 450883717216034179,
 (62, 33): 409894288378212890,
 (62, 34): 349615716557887465,
 (62, 35): 279692573246309972,
 (62, 36): 209769429934732479,
 (62, 37): 147405545359541742,
 (62, 38): 96977332473382725,
 (62, 39): 59678358445158600,
 (62, 40): 34315056105966195,
 (62, 41): 18412956934908690,
 (62, 42): 9206478467454345,
 (62, 43): 4282083008118300,
 (62, 44): 1849081298960175,
 (62, 45): 739632519584070,
 (62, 46): 273342452889765,
 (62, 47): 93052749919920,
 (62, 48): 29078984349975,
 (62, 49): 8308281242850,
 (62, 50): 2160153123141,
 (63, 13): 10468434365991,
 (63, 14): 37387265592825,
 (63, 15): 122131734269895,
 (63, 16): 366395202809685,
 (63, 17): 1012974972473835,
 (63, 18): 2588713818544245,
 (63, 19): 6131164307078475,
 (63, 20): 13488561475572645,
 (63, 21): 27619435402363035,
 (63, 22): 52728013040874885,
 (63, 23): 93993414551124795,
 (63, 24): 156655690918541325,
 (63, 25): 244382877832924467,
 (63, 26): 357174975294274221,
 (63, 27): 489462003181042451,
 (63, 28): 629308289804197437,
 (63, 29): 759510004936100355,
 (63, 30): 860778005594247069,
 (63, 31): 916312070471295267,
 (63, 32): 916312070471295267,
 (63, 33): 860778005594247069,
 (63, 34): 759510004936100355,
 (63, 35): 629308289804197437,
 (63, 36): 489462003181042451,
 (63, 37): 357174975294274221,
 (63, 38): 244382877832924467,
 (63, 39): 156655690918541325,
 (63, 40): 93993414551124795,
 (63, 41): 52728013040874885,
 (63, 42): 27619435402363035,
 (63, 43): 13488561475572645,
 (63, 44): 6131164307078475,
 (63, 45): 2588713818544245,
 (63, 46): 1012974972473835,
 (63, 47): 366395202809685,
 (63, 48): 122131734269895,
 (63, 49): 37387265592825,
 (63, 50): 10468434365991,
 (64, 14): 47855699958816,
 (64, 15): 159518999862720,
 (64, 16): 488526937079580,
 (64, 17): 1379370175283520,
 (64, 18): 3601688791018080,
 (64, 19): 8719878125622720,
 (64, 20): 19619725782651120,
 (64, 21): 41107996877935680,
 (64, 22): 80347448443237920,
 (64, 23): 146721427591999680,
 (64, 24): 250649105469666120,
 (64, 25): 401038568751465792,
 (64, 26): 601557853127198688,
 (64, 27): 846636978475316672,
 (64, 28): 1118770292985239888,
 (64, 29): 1388818294740297792,
 (64, 30): 1620288010530347424,
 (64, 31): 1777090076065542336,
 (64, 32): 1832624140942590534,
 (64, 33): 1777090076065542336,
 (64, 34): 1620288010530347424,
 (64, 35): 1388818294740297792,
 (64, 36): 1118770292985239888,
 (64, 37): 846636978475316672,
 (64, 38): 601557853127198688,
 (64, 39): 401038568751465792,
 (64, 40): 250649105469666120,
 (64, 41): 146721427591999680,
 (64, 42): 80347448443237920,
 (64, 43): 41107996877935680,
 (64, 44): 19619725782651120,
 (64, 45): 8719878125622720,
 (64, 46): 3601688791018080,
 (64, 47): 1379370175283520,
 (64, 48): 488526937079580,
 (64, 49): 159518999862720,
 (64, 50): 47855699958816,
 (65, 15): 207374699821536,
 (65, 16): 648045936942300,
 (65, 17): 1867897112363100,
 (65, 18): 4981058966301600,
 (65, 19): 12321566916640800,
 (65, 20): 28339603908273840,
 (65, 21): 60727722660586800,
 (65, 22): 121455445321173600,
 (65, 23): 227068876035237600,
 (65, 24): 397370533061665800,
 (65, 25): 651687674221131912,
 (65, 26): 1002596421878664480,
 (65, 27): 1448194831602515360,
 (65, 28): 1965407271460556560,
 (65, 29): 2507588587725537680,
 (65, 30): 3009106305270645216,
 (65, 31): 3397378086595889760,
 (65, 32): 3609714217008132870,
 (65, 33): 3609714217008132870,
 (65, 34): 3397378086595889760,
 (65, 35): 3009106305270645216,
 (65, 36): 2507588587725537680,
 (65, 37): 1965407271460556560,
 (65, 38): 1448194831602515360,
 (65, 39): 1002596421878664480,
 (65, 40): 651687674221131912,
 (65, 41): 397370533061665800,
 (65, 42): 227068876035237600,
 (65, 43): 121455445321173600,
 (65, 44): 60727722660586800,
 (65, 45): 28339603908273840,
 (65, 46): 12321566916640800,
 (65, 47): 4981058966301600,
 (65, 48): 1867897112363100,
 (65, 49): 648045936942300,
 (65, 50): 207374699821536,
 (66, 16): 855420636763836,
 (66, 17): 2515943049305400,
 (66, 18): 6848956078664700,
 (66, 19): 17302625882942400,
 (66, 20): 40661170824914640,
 (66, 21): 89067326568860640,
 (66, 22): 182183167981760400,
 (66, 23): 348524321356411200,
 (66, 24): 624439409096903400,
 (66, 25): 1049058207282797712,
 (66, 26): 1654284096099796392,
 (66, 27): 2450791253481179840,
 (66, 28): 3413602103063071920,
 (66, 29): 4472995859186094240,
 (66, 30): 5516694892996182896,
 (66, 31): 6406484391866534976,
 (66, 32): 7007092303604022630,
 (66, 33): 7219428434016265740,
 (66, 34): 7007092303604022630,
 (66, 35): 6406484391866534976,
 (66, 36): 5516694892996182896,
 (66, 37): 4472995859186094240,
 (66, 38): 3413602103063071920,
 (66, 39): 2450791253481179840,
 (66, 40): 1654284096099796392,
 (66, 41): 1049058207282797712,
 (66, 42): 624439409096903400,
 (66, 43): 348524321356411200,
 (66, 44): 182183167981760400,
 (66, 45): 89067326568860640,
 (66, 46): 40661170824914640,
 (66, 47): 17302625882942400,
 (66, 48): 6848956078664700,
 (66, 49): 2515943049305400,
 (66, 50): 855420636763836,
 (67, 17): 3371363686069236,
 (67, 18): 9364899127970100,
 (67, 19): 24151581961607100,
 (67, 20): 57963796707857040,
 (67, 21): 129728497393775280,
 (67, 22): 271250494550621040,
 (67, 23): 530707489338171600,
 (67, 24): 972963730453314600,
 (67, 25): 1673497616379701112,
 (67, 26): 2703342303382594104,
 (67, 27): 4105075349580976232,
 (67, 28): 5864393356544251760,
 (67, 29): 7886597962249166160,
 (67, 30): 9989690752182277136,
 (67, 31): 11923179284862717872,
 (67, 32): 13413576695470557606,
 (67, 33): 14226520737620288370,
 (67, 34): 14226520737620288370,
 (67, 35): 13413576695470557606,
 (67, 36): 11923179284862717872,
 (67, 37): 9989690752182277136,
 (67, 38): 7886597962249166160,
 (67, 39): 5864393356544251760,
 (67, 40): 4105075349580976232,
 (67, 41): 2703342303382594104,
 (67, 42): 1673497616379701112,
 (67, 43): 972963730453314600,
 (67, 44): 530707489338171600,
 (67, 45): 271250494550621040,
 (67, 46): 129728497393775280,
 (67, 47): 57963796707857040,
 (67, 48): 24151581961607100,
 (67, 49): 9364899127970100,
 (67, 50): 3371363686069236,
 (68, 18): 12736262814039336,
 (68, 19): 33516481089577200,
 (68, 20): 82115378669464140,
 (68, 21): 187692294101632320,
 (68, 22): 400978991944396320,
 (68, 23): 801957983888792640,
 (68, 24): 1503671219791486200,
 (68, 25): 2646461346833015712,
 (68, 26): 4376839919762295216,
 (68, 27): 6808417652963570336,
 (68, 28): 9969468706125227992,
 (68, 29): 13750991318793417920,
 (68, 30): 17876288714431443296,
 (68, 31): 21912870037044995008,
 (68, 32): 25336755980333275478,
 (68, 33): 27640097433090845976,
 (68, 34): 28453041475240576740,
 (68, 35): 27640097433090845976,
 (68, 36): 25336755980333275478,
 (68, 37): 21912870037044995008,
 (68, 38): 17876288714431443296,
 (68, 39): 13750991318793417920,
 (68, 40): 9969468706125227992,
 (68, 41): 6808417652963570336,
 (68, 42): 4376839919762295216,
 (68, 43): 2646461346833015712,
 (68, 44): 1503671219791486200,
 (68, 45): 801957983888792640,
 (68, 46): 400978991944396320,
 (68, 47): 187692294101632320,
 (68, 48): 82115378669464140,
 (68, 49): 33516481089577200,
 (68, 50): 12736262814039336,
 (69, 19): 46252743903616536,
 (69, 20): 115631859759041340,
 (69, 21): 269807672771096460,
 (69, 22): 588671286046028640,
 (69, 23): 1202936975833188960,
 (69, 24): 2305629203680278840,
 (69, 25): 4150132566624501912,
 (69, 26): 7023301266595310928,
 (69, 27): 11185257572725865552,
 (69, 28): 16777886359088798328,
 (69, 29): 23720460024918645912,
 (69, 30): 31627280033224861216,
 (69, 31): 39789158751476438304,
 (69, 32): 47249626017378270486,
 (69, 33): 52976853413424121454,
 (69, 34): 56093138908331422716,
 (69, 35): 56093138908331422716,
 (69, 36): 52976853413424121454,
 (69, 37): 47249626017378270486,
 (69, 38): 39789158751476438304,
 (69, 39): 31627280033224861216,
 (69, 40): 23720460024918645912,
 (69, 41): 16777886359088798328,
 (69, 42): 11185257572725865552,
 (69, 43): 7023301266595310928,
 (69, 44): 4150132566624501912,
 (69, 45): 2305629203680278840,
 (69, 46): 1202936975833188960,
 (69, 47): 588671286046028640,
 (69, 48): 269807672771096460,
 (69, 49): 115631859759041340,
 (69, 50): 46252743903616536,
 (70, 20): 161884603662657876,
 (70, 21): 385439532530137800,
 (70, 22): 858478958817125100,
 (70, 23): 1791608261879217600,
 (70, 24): 3508566179513467800,
 (70, 25): 6455761770304780752,
 (70, 26): 11173433833219812840,
 (70, 27): 18208558839321176480,
 (70, 28): 27963143931814663880,
 (70, 29): 40498346384007444240,
 (70, 30): 55347740058143507128,
 (70, 31): 71416438784701299520,
 (70, 32): 87038784768854708790,
 (70, 33): 100226479430802391940,
 (70, 34): 109069992321755544170,
 (70, 35): 112186277816662845432,
 (70, 36): 109069992321755544170,
 (70, 37): 100226479430802391940,
 (70, 38): 87038784768854708790,
 (70, 39): 71416438784701299520,
 (70, 40): 55347740058143507128,
 (70, 41): 40498346384007444240,
 (70, 42): 27963143931814663880,
 (70, 43): 18208558839321176480,
 (70, 44): 11173433833219812840,
 (70, 45): 6455761770304780752,
 (70, 46): 3508566179513467800,
 (70, 47): 1791608261879217600,
 (70, 48): 858478958817125100,
 (70, 49): 385439532530137800,
 (70, 50): 161884603662657876,
 (71, 21): 547324136192795676,
 (71, 22): 1243918491347262900,
 (71, 23): 2650087220696342700,
 (71, 24): 5300174441392685400,
 (71, 25): 9964327949818248552,
 (71, 26): 17629195603524593592,
 (71, 27): 29381992672540989320,
 (71, 28): 46171702771135840360,
 (71, 29): 68461490315822108120,
 (71, 30): 95846086442150951368,
 (71, 31): 126764178842844806648,
 (71, 32): 158455223553556008310,
 (71, 33): 187265264199657100730,
 (71, 34): 209296471752557936110,
 (71, 35): 221256270138418389602,
 (71, 36): 221256270138418389602,
 (71, 37): 209296471752557936110,
 (71, 38): 187265264199657100730,
 (71, 39): 158455223553556008310,
 (71, 40): 126764178842844806648,
 (71, 41): 95846086442150951368,
 (71, 42): 68461490315822108120,
 (71, 43): 46171702771135840360,
 (71, 44): 29381992672540989320,
 (71, 45): 17629195603524593592,
 (71, 46): 9964327949818248552,
 (71, 47): 5300174441392685400,
 (71, 48): 2650087220696342700,
 (71, 49): 1243918491347262900,
 (71, 50): 547324136192795676,
 (72, 22): 1791242627540058576,
 (72, 23): 3894005712043605600,
 (72, 24): 7950261662089028100,
 (72, 25): 15264502391210933952,
 (72, 26): 27593523553342842144,
 (72, 27): 47011188276065582912,
 (72, 28): 75553695443676829680,
 (72, 29): 114633193086957948480,
 (72, 30): 164307576757973059488,
 (72, 31): 222610265284995758016,
 (72, 32): 285219402396400814958,
 (72, 33): 345720487753213109040,
 (72, 34): 396561735952215036840,
 (72, 35): 430552741890976325712,
 (72, 36): 442512540276836779204,
 (72, 37): 430552741890976325712,
 (72, 38): 396561735952215036840,
 (72, 39): 345720487753213109040,
 (72, 40): 285219402396400814958,
 (72, 41): 222610265284995758016,
 (72, 42): 164307576757973059488,
 (72, 43): 114633193086957948480,
 (72, 44): 75553695443676829680,
 (72, 45): 47011188276065582912,
 (72, 46): 27593523553342842144,
 (72, 47): 15264502391210933952,
 (72, 48): 7950261662089028100,
 (72, 49): 3894005712043605600,
 (72, 50): 1791242627540058576,
 (73, 23): 5685248339583664176,
 (73, 24): 11844267374132633700,
 (73, 25): 23214764053299962052,
 (73, 26): 42858025944553776096,
 (73, 27): 74604711829408425056,
 (73, 28): 122564883719742412592,
 (73, 29): 190186888530634778160,
 (73, 30): 278940769844931007968,
 (73, 31): 386917842042968817504,
 (73, 32): 507829667681396572974,
 (73, 33): 630939890149613923998,
 (73, 34): 742282223705428145880,
 (73, 35): 827114477843191362552,
 (73, 36): 873065282167813104916,
 (73, 37): 873065282167813104916,
 (73, 38): 827114477843191362552,
 (73, 39): 742282223705428145880,
 (73, 40): 630939890149613923998,
 (73, 41): 507829667681396572974,
 (73, 42): 386917842042968817504,
 (73, 43): 278940769844931007968,
 (73, 44): 190186888530634778160,
 (73, 45): 122564883719742412592,
 (73, 46): 74604711829408425056,
 (73, 47): 42858025944553776096,
 (73, 48): 23214764053299962052,
 (73, 49): 11844267374132633700,
 (73, 50): 5685248339583664176,
 (74, 24): 17529515713716297876,
 (74, 25): 35059031427432595752,
 (74, 26): 66072789997853738148,
 (74, 27): 117462737773962201152,
 (74, 28): 197169595549150837648,
 (74, 29): 312751772250377190752,
 (74, 30): 469127658375565786128,
 (74, 31): 665858611887899825472,
 (74, 32): 894747509724365390478,
 (74, 33): 1138769557831010496972,
 (74, 34): 1373222113855042069878,
 (74, 35): 1569396701548619508432,
 (74, 36): 1700179760011004467468,
 (74, 37): 1746130564335626209832,
 (74, 38): 1700179760011004467468,
 (74, 39): 1569396701548619508432,
 (74, 40): 1373222113855042069878,
 (74, 41): 1138769557831010496972,
 (74, 42): 894747509724365390478,
 (74, 43): 665858611887899825472,
 (74, 44): 469127658375565786128,
 (74, 45): 312751772250377190752,
 (74, 46): 197169595549150837648,
 (74, 47): 117462737773962201152,
 (74, 48): 66072789997853738148,
 (74, 49): 35059031427432595752,
 (74, 50): 17529515713716297876,
 (75, 25): 52588547141148893628,
 (75, 26): 101131821425286333900,
 (75, 27): 183535527771815939300,
 (75, 28): 314632333323113038800,
 (75, 29): 509921367799528028400,
 (75, 30): 781879430625942976880,
 (75, 31): 1134986270263465611600,
 (75, 32): 1560606121612265215950,
 (75, 33): 2033517067555375887450,
 (75, 34): 2511991671686052566850,
 (75, 35): 2942618815403661578310,
 (75, 36): 3269576461559623975900,
 (75, 37): 3446310324346630677300,
 (75, 38): 3446310324346630677300,
 (75, 39): 3269576461559623975900,
 (75, 40): 2942618815403661578310,
 (75, 41): 2511991671686052566850,
 (75, 42): 2033517067555375887450,
 (75, 43): 1560606121612265215950,
 (75, 44): 1134986270263465611600,
 (75, 45): 781879430625942976880,
 (75, 46): 509921367799528028400,
 (75, 47): 314632333323113038800,
 (75, 48): 183535527771815939300,
 (75, 49): 101131821425286333900,
 (75, 50): 52588547141148893628,
 (76, 26): 153720368566435227528,
 (76, 27): 284667349197102273200,
 (76, 28): 498167861094928978100,
 (76, 29): 824553701122641067200,
 (76, 30): 1291800798425471005280,
 (76, 31): 1916865700889408588480,
 (76, 32): 2695592391875730827550,
 (76, 33): 3594123189167641103400,
 (76, 34): 4545508739241428454300,
 (76, 35): 5454610487089714145160,
 (76, 36): 6212195276963285554210,
 (76, 37): 6715886785906254653200,
 (76, 38): 6892620648693261354600,
 (76, 39): 6715886785906254653200,
 (76, 40): 6212195276963285554210,
 (76, 41): 5454610487089714145160,
 (76, 42): 4545508739241428454300,
 (76, 43): 3594123189167641103400,
 (76, 44): 2695592391875730827550,
 (76, 45): 1916865700889408588480,
 (76, 46): 1291800798425471005280,
 (76, 47): 824553701122641067200,
 (76, 48): 498167861094928978100,
 (76, 49): 284667349197102273200,
 (76, 50): 153720368566435227528,
 (77, 27): 438387717763537500728,
 (77, 28): 782835210292031251300,
 (77, 29): 1322721562217570045300,
 (77, 30): 2116354499548112072480,
 (77, 31): 3208666499314879593760,
 (77, 32): 4612458092765139416030,
 (77, 33): 6289715581043371930950,
 (77, 34): 8139631928409069557700,
 (77, 35): 10000119226331142599460,
 (77, 36): 11666805764052999699370,
 (77, 37): 12928082062869540207410,
 (77, 38): 13608507434599516007800,
 (77, 39): 13608507434599516007800,
 (77, 40): 12928082062869540207410,
 (77, 41): 11666805764052999699370,
 (77, 42): 10000119226331142599460,
 (77, 43): 8139631928409069557700,
 (77, 44): 6289715581043371930950,
 (77, 45): 4612458092765139416030,
 (77, 46): 3208666499314879593760,
 (77, 47): 2116354499548112072480,
 (77, 48): 1322721562217570045300,
 (77, 49): 782835210292031251300,
 (77, 50): 438387717763537500728,
 (78, 28): 1221222928055568752028,
 (78, 29): 2105556772509601296600,
 (78, 30): 3439076061765682117780,
 (78, 31): 5325020998862991666240,
 (78, 32): 7821124592080019009790,
 (78, 33): 10902173673808511346980,
 (78, 34): 14429347509452441488650,
 (78, 35): 18139751154740212157160,
 (78, 36): 21666924990384142298830,
 (78, 37): 24594887826922539906780,
 (78, 38): 26536589497469056215210,
 (78, 39): 27217014869199032015600,
 (78, 40): 26536589497469056215210,
 (78, 41): 24594887826922539906780,
 (78, 42): 21666924990384142298830,
 (78, 43): 18139751154740212157160,
 (78, 44): 14429347509452441488650,
 (78, 45): 10902173673808511346980,
 (78, 46): 7821124592080019009790,
 (78, 47): 5325020998862991666240,
 (78, 48): 3439076061765682117780,
 (78, 49): 2105556772509601296600,
 (78, 50): 1221222928055568752028,
 (79, 29): 3326779700565170048628,
 (79, 30): 5544632834275283414380,
 (79, 31): 8764097060628673784020,
 (79, 32): 13146145590943010676030,
 (79, 33): 18723298265888530356770,
 (79, 34): 25331521183260952835630,
 (79, 35): 32569098664192653645810,
 (79, 36): 39806676145124354455990,
 (79, 37): 46261812817306682205610,
 (79, 38): 51131477324391596121990,
 (79, 39): 53753604366668088230810,
 (79, 40): 53753604366668088230810,
 (79, 41): 51131477324391596121990,
 (79, 42): 46261812817306682205610,
 (79, 43): 39806676145124354455990,
 (79, 44): 32569098664192653645810,
 (79, 45): 25331521183260952835630,
 (79, 46): 18723298265888530356770,
 (79, 47): 13146145590943010676030,
 (79, 48): 8764097060628673784020,
 (79, 49): 5544632834275283414380,
 (79, 50): 3326779700565170048628,
 (80, 30): 8871412534840453463008,
 (80, 31): 14308729894903957198400,
 (80, 32): 21910242651571684460050,
 (80, 33): 31869443856831541032800,
 (80, 34): 44054819449149483192400,
 (80, 35): 57900619847453606481440,
 (80, 36): 72375774809317008101800,
 (80, 37): 86068488962431036661600,
 (80, 38): 97393290141698278327600,
 (80, 39): 104885081691059684352800,
 (80, 40): 107507208733336176461620,
 (80, 41): 104885081691059684352800,
 (80, 42): 97393290141698278327600,
 (80, 43): 86068488962431036661600,
 (80, 44): 72375774809317008101800,
 (80, 45): 57900619847453606481440,
 (80, 46): 44054819449149483192400,
 (80, 47): 31869443856831541032800,
 (80, 48): 21910242651571684460050,
 (80, 49): 14308729894903957198400,
 (80, 50): 8871412534840453463008,
 (81, 31): 23180142429744410661408,
 (81, 32): 36218972546475641658450,
 (81, 33): 53779686508403225492850,
 (81, 34): 75924263305981024225200,
 (81, 35): 101955439296603089673840,
 (81, 36): 130276394656770614583240,
 (81, 37): 158444263771748044763400,
 (81, 38): 183461779104129314989200,
 (81, 39): 202278371832757962680400,
 (81, 40): 212392290424395860814420,
 (81, 41): 212392290424395860814420,
 (81, 42): 202278371832757962680400,
 (81, 43): 183461779104129314989200,
 (81, 44): 158444263771748044763400,
 (81, 45): 130276394656770614583240,
 (81, 46): 101955439296603089673840,
 (81, 47): 75924263305981024225200,
 (81, 48): 53779686508403225492850,
 (81, 49): 36218972546475641658450,
 (81, 50): 23180142429744410661408,
 (82, 32): 59399114976220052319858,
 (82, 33): 89998659054878867151300,
 (82, 34): 129703949814384249718050,
 (82, 35): 177879702602584113899040,
 (82, 36): 232231833953373704257080,
 (82, 37): 288720658428518659346640,
 (82, 38): 341906042875877359752600,
 (82, 39): 385740150936887277669600,
 (82, 40): 414670662257153823494820,
 (82, 41): 424784580848791721628840,
 (82, 42): 414670662257153823494820,
 (82, 43): 385740150936887277669600,
 (82, 44): 341906042875877359752600,
 (82, 45): 288720658428518659346640,
 (82, 46): 232231833953373704257080,
 (82, 47): 177879702602584113899040,
 (82, 48): 129703949814384249718050,
 (82, 49): 89998659054878867151300,
 (82, 50): 59399114976220052319858,
 (83, 33): 149397774031098919471158,
 (83, 34): 219702608869263116869350,
 (83, 35): 307583652416968363617090,
 (83, 36): 410111536555957818156120,
 (83, 37): 520952492381892363603720,
 (83, 38): 630626701304396019099240,
 (83, 39): 727646193812764637422200,
 (83, 40): 800410813194041101164420,
 (83, 41): 839455243105945545123660,
 (83, 42): 839455243105945545123660,
 (83, 43): 800410813194041101164420,
 (83, 44): 727646193812764637422200,
 (83, 45): 630626701304396019099240,
 (83, 46): 520952492381892363603720,
 (83, 47): 410111536555957818156120,
 (83, 48): 307583652416968363617090,
 (83, 49): 219702608869263116869350,
 (83, 50): 149397774031098919471158,
 (84, 34): 369100382900362036340508,
 (84, 35): 527286261286231480486440,
 (84, 36): 717695188972926181773210,
 (84, 37): 931064028937850181759840,
 (84, 38): 1151579193686288382702960,
 (84, 39): 1358272895117160656521440,
 (84, 40): 1528057007006805738586620,
 (84, 41): 1639866056299986646288080,
 (84, 42): 1678910486211891090247320,
 (84, 43): 1639866056299986646288080,
 (84, 44): 1528057007006805738586620,
 (84, 45): 1358272895117160656521440,
 (84, 46): 1151579193686288382702960,
 (84, 47): 931064028937850181759840,
 (84, 48): 717695188972926181773210,
 (84, 49): 527286261286231480486440,
 (84, 50): 369100382900362036340508,
 (85, 35): 896386644186593516826948,
 (85, 36): 1244981450259157662259650,
 (85, 37): 1648759217910776363533050,
 (85, 38): 2082643222624138564462800,
 (85, 39): 2509852088803449039224400,
 (85, 40): 2886329902123966395108060,
 (85, 41): 3167923063306792384874700,
 (85, 42): 3318776542511877736535400,
 (85, 43): 3318776542511877736535400,
 (85, 44): 3167923063306792384874700,
 (85, 45): 2886329902123966395108060,
 (85, 46): 2509852088803449039224400,
 (85, 47): 2082643222624138564462800,
 (85, 48): 1648759217910776363533050,
 (85, 49): 1244981450259157662259650,
 (85, 50): 896386644186593516826948,
 (86, 36): 2141368094445751179086598,
 (86, 37): 2893740668169934025792700,
 (86, 38): 3731402440534914927995850,
 (86, 39): 4592495311427587603687200,
 (86, 40): 5396181990927415434332460,
 (86, 41): 6054252965430758779982760,
 (86, 42): 6486699605818670121410100,
 (86, 43): 6637553085023755473070800,
 (86, 44): 6486699605818670121410100,
 (86, 45): 6054252965430758779982760,
 (86, 46): 5396181990927415434332460,
 (86, 47): 4592495311427587603687200,
 (86, 48): 3731402440534914927995850,
 (86, 49): 2893740668169934025792700,
 (86, 50): 2141368094445751179086598,
 (87, 37): 5035108762615685204879298,
 (87, 38): 6625143108704848953788550,
 (87, 39): 8323897751962502531683050,
 (87, 40): 9988677302355003038019660,
 (87, 41): 11450434956358174214315220,
 (87, 42): 12540952571249428901392860,
 (87, 43): 13124252690842425594480900,
 (87, 44): 13124252690842425594480900,
 (87, 45): 12540952571249428901392860,
 (87, 46): 11450434956358174214315220,
 (87, 47): 9988677302355003038019660,
 (87, 48): 8323897751962502531683050,
 (87, 49): 6625143108704848953788550,
 (87, 50): 5035108762615685204879298,
 (88, 38): 11660251871320534158667848,
 (88, 39): 14949040860667351485471600,
 (88, 40): 18312575054317505569702710,
 (88, 41): 21439112258713177252334880,
 (88, 42): 23991387527607603115708080,
 (88, 43): 25665205262091854495873760,
 (88, 44): 26248505381684851188961800,
 (88, 45): 25665205262091854495873760,
 (88, 46): 23991387527607603115708080,
 (88, 47): 21439112258713177252334880,
 (88, 48): 18312575054317505569702710,
 (88, 49): 14949040860667351485471600,
 (88, 50): 11660251871320534158667848,
 (89, 39): 26609292731987885644139448,
 (89, 40): 33261615914984857055174310,
 (89, 41): 39751687313030682822037590,
 (89, 42): 45430499786320780368042960,
 (89, 43): 49656592789699457611581840,
 (89, 44): 51913710643776705684835560,
 (89, 45): 51913710643776705684835560,
 (89, 46): 49656592789699457611581840,
 (89, 47): 45430499786320780368042960,
 (89, 48): 39751687313030682822037590,
 (89, 49): 33261615914984857055174310,
 (89, 50): 26609292731987885644139448,
 (90, 40): 59870908646972742699313758,
 (90, 41): 73013303228015539877211900,
 (90, 42): 85182187099351463190080550,
 (90, 43): 95087092576020237979624800,
 (90, 44): 101570303433476163296417400,
 (90, 45): 103827421287553411369671120,
 (90, 46): 101570303433476163296417400,
 (90, 47): 95087092576020237979624800,
 (90, 48): 85182187099351463190080550,
 (90, 49): 73013303228015539877211900,
 (90, 50): 59870908646972742699313758,
 (91, 41): 132884211874988282576525658,
 (91, 42): 158195490327367003067292450,
 (91, 43): 180269279675371701169705350,
 (91, 44): 196657396009496401276042200,
 (91, 45): 205397724721029574666088520,
 (91, 46): 205397724721029574666088520,
 (91, 47): 196657396009496401276042200,
 (91, 48): 180269279675371701169705350,
 (91, 49): 158195490327367003067292450,
 (91, 50): 132884211874988282576525658,
 (92, 42): 291079702202355285643818108,
 (92, 43): 338464770002738704236997800,
 (92, 44): 376926675684868102445747550,
 (92, 45): 402055120730525975942130720,
 (92, 46): 410795449442059149332177040,
 (92, 47): 402055120730525975942130720,
 (92, 48): 376926675684868102445747550,
 (92, 49): 338464770002738704236997800,
 (92, 50): 291079702202355285643818108,
 (93, 43): 629544472205093989880815908,
 (93, 44): 715391445687606806682745350,
 (93, 45): 778981796415394078387878270,
 (93, 46): 812850570172585125274307760,
 (93, 47): 812850570172585125274307760,
 (93, 48): 778981796415394078387878270,
 (93, 49): 715391445687606806682745350,
 (93, 50): 629544472205093989880815908,
 (94, 44): 1344935917892700796563561258,
 (94, 45): 1494373242103000885070623620,
 (94, 46): 1591832366587979203662186030,
 (94, 47): 1625701140345170250548615520,
 (94, 48): 1591832366587979203662186030,
 (94, 49): 1494373242103000885070623620,
 (94, 50): 1344935917892700796563561258,
 (95, 45): 2839309159995701681634184878,
 (95, 46): 3086205608690980088732809650,
 (95, 47): 3217533506933149454210801550,
 (95, 48): 3217533506933149454210801550,
 (95, 49): 3086205608690980088732809650,
 (95, 50): 2839309159995701681634184878,
 (96, 46): 5925514768686681770366994528,
 (96, 47): 6303739115624129542943611200,
 (96, 48): 6435067013866298908421603100,
 (96, 49): 6303739115624129542943611200,
 (96, 50): 5925514768686681770366994528,
 (97, 47): 12229253884310811313310605728,
 (97, 48): 12738806129490428451365214300,
 (97, 49): 12738806129490428451365214300,
 (97, 50): 12229253884310811313310605728,
 (98, 48): 24968060013801239764675820028,
 (98, 49): 25477612258980856902730428600,
 (98, 50): 24968060013801239764675820028,
 (99, 49): 50445672272782096667406248628,
 (99, 50): 50445672272782096667406248628,
 (100, 50): 100891344545564193334812497256}

Programmation dynamique


In [1]:
def binomrow(n):
    row = [1]
    for r in range(n):
        row = [1] + [row[i-1]+row[i] for i in range(1, r+1)] + [1]
    return row

In [2]:
[binomrow(i) for i in range(10)]


Out[2]:
[[1],
 [1, 1],
 [1, 2, 1],
 [1, 3, 3, 1],
 [1, 4, 6, 4, 1],
 [1, 5, 10, 10, 5, 1],
 [1, 6, 15, 20, 15, 6, 1],
 [1, 7, 21, 35, 35, 21, 7, 1],
 [1, 8, 28, 56, 70, 56, 28, 8, 1],
 [1, 9, 36, 84, 126, 126, 84, 36, 9, 1]]

In [3]:
binomrow(100)[50]


Out[3]:
100891344545564193334812497256

In [ ]:


In [ ]:

Les permutations


In [3]:
def listPerm(l): # Hypothese l est trie
    if not l:   # l != []
        return [[]]
    res = []
    for i in range(len(l)):
        x = l[i]
        ll = list(l)
        del ll[i]
        res.extend([x]+sol for sol in listPerm(ll))
    return res

In [4]:
listPerm([])


Out[4]:
[[]]

In [5]:
listPerm([1])


Out[5]:
[[1]]

In [6]:
listPerm([1,2,3])


Out[6]:
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

In [7]:
def iterPerm(l):
    if not l:
        yield []
    else:
        for i in range(len(l)):
            x = l[i]
            ll = list(l)
            del ll[i]
            for sol in listPerm(ll):
                yield [x]+sol

In [8]:
list(iterPerm([1,2,3]))


Out[8]:
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

In [9]:
listPerm(range(7)) == list(iterPerm(range(7)))


Out[9]:
True

In [ ]:


In [ ]:


In [ ]:


In [10]:
def unrank_perm(l, r):
    if not l:
        if r == 0:
            return []
        else:
            raise IndexError
    reccard = factorial(len(l)-1)
    ifirst = r // reccard
    irec = r % reccard
    l = l[:]
    first = l[ifirst]
    del l[ifirst]
    return [first] + unrank_perm(l, irec)

In [11]:
unrank_perm([1,2,3,4,5], 12)


Out[11]:
[1, 4, 2, 3, 5]

In [14]:
N = 6
[unrank_perm(range(N), i) for i in range(factorial(N))] == listPerm(range(N))


Out[14]:
True

In [ ]:

Les multipermutations


In [8]:
def multinom(l):
    return factorial(sum(l)) / prod(factorial(i) for i in l)

In [9]:
multinom((3,1,0,2))


Out[9]:
60

In [10]:
def unrank_multi(l, r):
    if sum(l) == 0:
        if r == 0:
            return []
        else:
            raise IndexError
    for i in range(len(l)):
        if l[i] > 0:
            l[i] -= 1 
            reccard = multinom(l)
            if r < reccard:
                return [i] + unrank_multi(l, r)
            l[i] += 1
            r -= reccard
    raise IndexError

In [11]:
unrank_multi([3,1,0,2], 45)


Out[11]:
[3, 0, 0, 3, 1, 0]

In [12]:
MS = [3,1,1] 
[unrank_multi(MS[:], i) for i in range(multinom(MS))]


Out[12]:
[[0, 0, 0, 1, 2],
 [0, 0, 0, 2, 1],
 [0, 0, 1, 0, 2],
 [0, 0, 1, 2, 0],
 [0, 0, 2, 0, 1],
 [0, 0, 2, 1, 0],
 [0, 1, 0, 0, 2],
 [0, 1, 0, 2, 0],
 [0, 1, 2, 0, 0],
 [0, 2, 0, 0, 1],
 [0, 2, 0, 1, 0],
 [0, 2, 1, 0, 0],
 [1, 0, 0, 0, 2],
 [1, 0, 0, 2, 0],
 [1, 0, 2, 0, 0],
 [1, 2, 0, 0, 0],
 [2, 0, 0, 0, 1],
 [2, 0, 0, 1, 0],
 [2, 0, 1, 0, 0],
 [2, 1, 0, 0, 0]]

In [ ]:


In [ ]:


In [ ]: