Codeforces Beta Round 76 (Div. 1 Only) |
---|
Закончено |
Будучи первокурсником, Игорь К., как и все остальные, по строгому указанию преподавателя решал олимпиадные задачи по программированию. Однажды его внимание привлекла задача "Флаги" на сайте Timmy's Online Judge. В ней требовалось найти количество трехцветных флагов, удовлетворяющих условию... впрочем, это неважно. Игорь К. быстро подобрал формулу и получил заветный Accepted.
Однако преподавателя это не сильно впечатлило. Он решил, что задача, представленная на Timmy's Online Judge, очень скучная и простая: всего три возможных цвета полос, всего два ограничения. Он поставил перед Игорем К. усложненную задачу, и тот не смог ее решить. Мы, конечно, умолчим о том, что преподаватель сам не смог ее решить.
А вы сможете?
Флаги состоят из одной или нескольких параллельных полос одинаковой ширины. Полосы могут быть одного из следующих четырех цветов: белого, черного, красного или желтого. Требуется найти количество различных флагов с числом полос от L до R, если:
В единственной строке записаны два целых числа L и R (1 ≤ L ≤ R ≤ 109) — нижняя и верхняя границы количества полос на флаге.
Выведите единственное число — количество различных флагов, удовлетворяющих условию задачи и имеющих от L до R полос, по модулю 1000000007.
3 4
23
5 6
64
В первом тесте существуют такие флаги (они перечислены в лексикографическом порядке, буквами B, R, W, Y обозначены соответственно черный, красный, белый и желтый цвета):
3 полосы: BWB, BYB, BYR, RWR, RYR, WBW, WBY, WRW, WRY, YBY, YRY (всего 11 флагов).
4 полосы: BWBW, BWBY, BYBW, BYBY, BYRW, BYRY, RWRW, RWRY, RYBW, RYBY, RYRW, RYRY (12 флагов).
Поэтому ответ на тест 1 равен 11 + 12 = 23.
Название |
---|