D. Флаги
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Будучи первокурсником, Игорь К., как и все остальные, по строгому указанию преподавателя решал олимпиадные задачи по программированию. Однажды его внимание привлекла задача "Флаги" на сайте Timmy's Online Judge. В ней требовалось найти количество трехцветных флагов, удовлетворяющих условию... впрочем, это неважно. Игорь К. быстро подобрал формулу и получил заветный Accepted.

Однако преподавателя это не сильно впечатлило. Он решил, что задача, представленная на Timmy's Online Judge, очень скучная и простая: всего три возможных цвета полос, всего два ограничения. Он поставил перед Игорем К. усложненную задачу, и тот не смог ее решить. Мы, конечно, умолчим о том, что преподаватель сам не смог ее решить.

А вы сможете?

Флаги состоят из одной или нескольких параллельных полос одинаковой ширины. Полосы могут быть одного из следующих четырех цветов: белого, черного, красного или желтого. Требуется найти количество различных флагов с числом полос от L до R, если:

  • в флаге не может быть полос одного цвета, расположенных рядом;
  • в флаге не может быть полос белого и желтого цветов, расположенных рядом;
  • в флаге не может быть полос красного и черного цветов, расположенных рядом;
  • в флаге не может быть сочетания полос черного, белого и красного цветов, расположенных подряд в этом или обратном порядке;
  • симметричные флаги (как, например, WB и BW, где буквами W и B обозначены белый и черный цвета) считаются одинаковыми.
Входные данные

В единственной строке записаны два целых числа 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.