Прокопатели — известная музыкальная группа, поэтому уже 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 (10⁹ + 7).