A. Организация фестиваля
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Прокопатели — известная музыкальная группа, поэтому уже 80 лет их приглашают на фестиваль ENTER, чтобы выступить в качестве неожиданных гостей. В начале своей карьеры они были не так успешны, поэтому зарабатывали на жизнь копанием каналов, откуда и произошло название группы. В любом случае, они очень любят ездить в турне, и их энергии хватает на невероятно долгие поездки. Однако, они терпеть не могут проводить два последовательных дня не давая концерта, поэтому стараются избегать такой ситуации.

Турне определяется как последовательность концертов и выходных дней. Требуется посчитать количество способов выбрать k различных турне одинаковой длины между l и r.

Например, пусть k = 2, l = 1 и r = 2. Будем обозначать день с концертом как {1}, а выходной как {0}. Возможными турами являются: {0}, {1}, {00}, {01}, {10}, {11}, но тур {00} не подходит, поскольку содержит два выходных дня подряд. Теперь найдём количество способов выбрать k = 2 тура одинаковой длины в диапазоне длин [1;2]. Перечислим их: {0,1}; {01,10}; {01,11}; {10,11}.

Поскольку расписание Прокопателей уже достаточно плотно занято, то они просят вас посчитать ответ по модулю 1 000 000 007 (109 + 7).

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

В первой строке входных данных записаны три целых числа k, l и r (1 ≤ k ≤ 200, 1 ≤ l ≤ r ≤ 1018).

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

Выведите одно целое число: остаток от деления количества способов выбрать k различных туров одинаковой длины на 1 000 000 007.

Пример
Входные данные
1 1 2
Выходные данные
5