Две контрольные точки

Время 2 с · память 256 МБ

Исполнитель преобразует целое число на экране. A прибавляет 1. B умножает на 2.

Найдите число программ из A в B, проходящих через C, а затем через D. Начальное и конечное числа тоже относятся к траектории.

Пустая программа допустима и считается одной программой, если начальное число уже равно конечному и остальные ограничения выполнены. Разные последовательности команд считаются разными программами, даже если дают одинаковую траекторию.

Входные данные

Четыре целых числа A, B, C и D: 1 ≤ A ≤ C < D ≤ B ≤ 60.

Выходные данные

Выведите одно целое число — количество подходящих программ. Если таких программ нет, выведите 0.

Примеры

Ввод 1
1 4 2 3
Вывод 1
2
Ввод 2
2 8 3 6
Вывод 2
2

Примечание

Для 1 → 2 → 3 → 4 получаем 2 × 1 × 1 = 2 программы: AAA и BAA. Во втором примере 2 → 3 возможно только прибавлением, 3 → 6 — тремя прибавлениями или умножением, 6 → 8 — двумя прибавлениями. Ответ 2.

Решение
Загрузка редактора…
Результат появится здесь

Черновик сохраняется в этом браузере.

Ошибка в задаче