def recursion_zenik(n,k,path=[],debug=False):
    if path and max(path)-min(path)>k:
        if debug:
            print('Zenik rule fail:',path)
        return 0
    if n==0:
        if debug:
            print('Success:',path)
        return 1
    return sum(recursion_zenik(n-i,k,path+[i]) for i in range(1,n+1))

def matrix_zenik(n,k, debug = False):
    matrix = []
    for step in range(n+1):
        line = [0]*(step+2)
        matrix.append([line[:] for _ in range(n+1)])
        matrix[step][step][step] = 1 #we have 1 way to step from the land on each step
    
    for step_from in range(1,n):
        for step_to in range(step_from+1,n+1):
            for min_i in range(1,step_from+2):
                for max_i in range(min_i,min(min_i+k,step_from+1)+1):                
                    min_to_write = min(min_i,step_to-step_from)
                    max_to_write = max(max_i,step_to-step_from)
                    if max_to_write-min_to_write<=k:
                        matrix[step_to][min_to_write][max_to_write] += matrix[step_from][min_i][max_i]
                    
    if debug:
        for step in range(n+1):
            print(step,':',',\n'.join(str(line) for line in matrix[step]))
    return sum(sum(line) for line in matrix[n])

def check_equal_rec_mat(s):
    for n in range(1,s):
        for k in range(1,s):
            rec = recursion_zenik(n,k)
            mat = matrix_zenik(n,k)
            if rec!=mat:
                print('\nFAIL: n=',n,'k=',k,'rec=',rec,'mat=',mat)
            else:
                print('OK',end=' ')
    print()

#print('Result =',recursion_zenik(4, 2, debug=False))
#print('Result =',matrix_zenik(4,2,debug=True))
#check_equal_rec_mat(15)
import time
t = time.clock()
print(matrix_zenik(100,100))
print('time = ',time.clock()-t)