Обойти запрещённое число
Исполнитель преобразует целое число на экране. A прибавляет 1. B умножает на 2.
Найдите число программ из A в B, в траектории которых нет X. Начальное и конечное числа тоже относятся к траектории.
Пустая программа допустима и считается одной программой, если начальное число уже равно конечному и остальные ограничения выполнены. Разные последовательности команд считаются разными программами, даже если дают одинаковую траекторию.
Входные данные
Три целых числа A, B и X: 1 ≤ A ≤ B ≤ 60, 1 ≤ X ≤ 60.
Выходные данные
Выведите одно целое число — количество подходящих программ. Если таких программ нет, выведите 0.
Примеры
1 4 3
2
2 7 4
1
Примечание
Из 1 в 4 подходят AB и BB: они обходят 3, умножая 2 сразу до 4. Программы AAA и BAA проходят через 3 и не подходят. Во втором примере запрещено число 4: остаётся только путь 2 → 3 → 6 → 7, то есть ABA.