''' 1)  У исполнителя Калькулятор две команды, которым присвоены номера:

1. прибавь 1

2. умножь на 2

Сколько есть программ, которые число 1 преобразуют в число 16?

+1  *2   1 -> 16

Рассмотрим задачу на примере

1 -> 6
1+1+1+1+1+1
(1+1+1)*2
1*2*2+1+1
(1+1)*2+1+1
1*2+1+1+1+1
(1*2+1)*2

Получили 6 программ

Обозначим:    st = 1, ..., 6 = fin

'''

def f(st, fin):
    if st == fin:
        return 1
    if st > fin:
        return 0
    return f(st+1, fin) + f(st*2, fin)
    
res = f(1, 6)
print(res)


'''
2)	У исполнителя Калькулятор две команды, которым присвоены номера:
1. прибавь 1
2. умножь на 4
Сколько есть программ, которые число 1 преобразуют в число 55?  

'''