Программы робота через контрольную точку

В кружке робототехники есть исполнитель «Робот-Число». Он держит на табло целое число и умеет выполнять команды:

• +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