Через нужное число
Исполнитель преобразует целое число на экране. A прибавляет 1. B умножает на 2.
Найдите число программ из A в B, траектория которых содержит C. Начальное и конечное числа тоже относятся к траектории.
Пустая программа допустима и считается одной программой, если начальное число уже равно конечному и остальные ограничения выполнены. Разные последовательности команд считаются разными программами, даже если дают одинаковую траекторию.
Входные данные
Три целых числа A, B и C: 1 ≤ A ≤ C ≤ B ≤ 60.
Выходные данные
Выведите одно целое число — количество подходящих программ. Если таких программ нет, выведите 0.
Примеры
1 4 2
4
2 7 4
2
Примечание
Из 1 в 2 можно попасть командами A или B: два варианта. Из 2 в 4 — AA или B: ещё два. Соединяем части и получаем четыре программы. Во втором примере до 4 из 2 есть две программы, а из 4 до 7 — только AAA: ответ 2.