정우는 깃발을 그리는 취미를 가지고 있다.

아무리 취미 생활이라지만 평소 자기가 가지고 있는 완벽주의자적 기질에 따라 깃발을 그리는데 규칙을 정했다.

• 깃발은 n개의 연속된 가로 줄무늬로 이루어져 있다.
• 줄무늬는 검정(B), 하양(W), 노랑(Y), 빨강(R) 색으로만 칠할 수 있다.
• 인접한 줄무늬의 색은 같을 수 없다.
• 하얀색과 노랑색은 인접해 있을 수 없다.
• 빨간색과 검정색은 인접해 있을 수 없다.
• 검정색, 흰색, 빨간색의 조합은 있을 수 없다. (조합의 예: BWR, WBR, RWB, RBW 등)
• 앞 뒤로 뒤집었을 때 같은 깃발은 하나로 친다. (예: BW와 WB는 같은 깃발)

정우는 f(n) 값이 궁금했는데, 좀더 문제를 심화시켜 f(L)+f(L+1)+...+f(R-1)+f(R) 을 1,000,000,007 로 나눈 나머지 값을 구하려한다.

입력

출력

입출력 예

입력 

3 4

출력 

23

입력 

5 6

출력 

64

출처: Codeforces Beta Round #76 Div 1
추천: tamaki