Две контрольные точки
Исполнитель преобразует целое число на экране. A прибавляет 1. B умножает на 2.
Найдите число программ из A в B, проходящих через C, а затем через D. Начальное и конечное числа тоже относятся к траектории.
Пустая программа допустима и считается одной программой, если начальное число уже равно конечному и остальные ограничения выполнены. Разные последовательности команд считаются разными программами, даже если дают одинаковую траекторию.
Входные данные
Четыре целых числа A, B, C и D: 1 ≤ A ≤ C < D ≤ B ≤ 60.
Выходные данные
Выведите одно целое число — количество подходящих программ. Если таких программ нет, выведите 0.
Примеры
1 4 2 3
2
2 8 3 6
2
Примечание
Для 1 → 2 → 3 → 4 получаем 2 × 1 × 1 = 2 программы: AAA и BAA. Во втором примере 2 → 3 возможно только прибавлением, 3 → 6 — тремя прибавлениями или умножением, 6 → 8 — двумя прибавлениями. Ответ 2.