Программы робота через контрольную точку
Условие
В кружке робототехники есть исполнитель «Робот-Число». Он держит на табло целое число и умеет выполнять команды:
+1(увеличить число на 1)*2(умножить число на 2)
Робота запускают со значения A и хотят получить значение B. Программа — это последовательность команд (она может быть пустой). По правилам безопасности робот обязан хотя бы один раз оказаться на значении C во время выполнения программы (включая самое начало и самый конец).
Посчитайте, сколько существует разных программ, которые переводят A в B и при этом проходят через C. Так как программ может быть очень много, выведите ответ по модулю 10^9+7.
Формат ввода Одной строкой вводятся три целых числа A B C.
Формат вывода Выведите одно целое число — количество программ по модулю 1000000007.
Ограничения
1 ≤ A ≤ C ≤ B ≤ 10^6- ответ выводить по модулю
10^9+7
Пример Ввод: 2 10 5
Вывод: 4
Решить задачу с автопроверкой на Python →
Куда дальше
- Школьный этап ВсОШ по информатике — как устроен первый этап и план подготовки за четыре недели
- Python на олимпиадах — где языка хватает с запасом, а где начинают значить лимиты — с замерами
- Родителям: подготовка бесплатно — сколько стоит репетитор, что даёт бесплатный маршрут и как понять, что ребёнок занимается