1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
MODULE = 10 ** 9 + 7
memo_1 = {}
def get(n):
    if n <= 0:
        return 1
    if n not in memo_1:
        result = sum(get(i) * get(n-i-1) for i in xrange(n))
        memo_1[n] = result % MODULE
    return memo_1[n]
memo_2 = {}
def get_pair(n, k):
    if k == 0:
        return 0
    if k == 1:
        return get(n)
    if n == 0:
        return 1
    if (n, k) not in memo_2:
        result = sum(get(n-i) * get_pair(i, k-1)  for i in xrange(n+1))
        memo_2[(n, k)] = result % MODULE
    return memo_2[(n, k)]
while True:
    try:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX