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

1. прибавь 1

2. умножь на 2

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

+1  *2   1 -> 16

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

1 -> 6       1->3->6  1->!4->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

'''

# 1 -> 6 !!! 
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)

#=================

# 1 -> 3 -> 6 !!! 
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, 3) * f(3, 6)  # Изменять ЗДЕСЬ!
print(res)


#=================
# =  1 -> !4 -> 6
def f(st, fin):
    if st == fin:
        return 1
    if st > fin or st == 4:  # Изменять ЗДЕСЬ!
        return 0
    return f(st+1, fin) + f(st*2, fin)
    
res = f(1, 6)
print(res)

#  1 -> 5 -> 9 -> !13 -> 30

# ЕГЭ-23: 338, 339, 340