깃발

When Igor K.가 신입생이었을 때, 교수는 그를 비롯한 모든 신입생에게 프로그래밍 올림피아드 문제를 풀라고 엄하게 권했다. 어느 날 Timmy's Online Judge라는 웹사이트의 "Flags"라는 문제가 그의 관심을 끌었다. 그 문제에서는 조건을 만족하는 세 가지 색으로 된 깃발의 개수를 구해야 했는데... 사실 그것은 중요하지 않다. Igor K.는 빠르게 공식을 찾아내고 그토록 간절히 바라던 Accepted를 받았다.

하지만 교수는 별로 감명받지 않았다. 그는 Timmy's Online Judge에 실린 문제가 매우 지루하고 간단하다고 판단했다. 깃발 줄무늬에 사용할 수 있는 색이 세 가지뿐이고 제한도 두 개뿐이었기 때문이다. 그는 Igor K.에게 복잡한 문제를 제안했고, 그는 그 문제를 풀지 못했다. 물론 교수 역시 풀지 못했다는 사실은 아무에게도 말하지 않을 것이다.

여러분은 어떤가? 이 문제를 풀 수 있는가?

깃발은 폭이 같은 하나 또는 여러 개의 평행한 줄무늬로 이루어진다. 줄무늬는 흰색, 검은색, 빨간색 또는 노란색 중 하나일 수 있다. 다음 조건을 만족하며 줄무늬 수가 L부터 R까지인 서로 다른 깃발의 개수를 구해야 한다.

• 깃발에서 같은 색의 줄무늬가 서로 인접할 수 없다.
• 깃발에서 흰색 줄무늬와 노란색 줄무늬가 서로 인접할 수 없다.
• 깃발에서 빨간색 줄무늬와 검은색 줄무늬가 서로 인접할 수 없다.
• 깃발에는 검은색, 흰색, 빨간색 줄무늬가 이 순서 또는 역순으로 연달아 나오는 조합이 있을 수 없다.
• 대칭인 깃발은 같은 것으로 간주한다(예를 들어 W and B가 흰색과 검은색을 나타낼 때, WB 깃발과 BW 깃발은 같은 것으로 간주한다).

유일한 줄에 두 정수 L and R (1 ≤ L ≤ R ≤ 109)이 주어진다. 이들은 깃발의 줄무늬 수에 대한 하한과 상한이다.

문제의 조건을 만족하고 줄무늬 수가 L부터 R까지인 서로 다른 깃발의 개수를 1000000007로 나눈 나머지를 하나의 수로 출력한다.

첫 번째 테스트에는 다음과 같은 깃발이 존재한다(사전순으로 나열했으며, 문자 B, R, W, Y는 각각 검은색, 빨간색, White and Yellow을 나타낸다).

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이다.