CF93D.Flags

When Igor K. was a freshman, his professor strictly urged him, as well as all other freshmen, to solve programming Olympiads. One day a problem called "Flags" from a website called Timmy's Online Judge caught his attention. In the problem one had to find the number of three-colored flags that would satisfy the condition... actually, it doesn't matter. Igor K. quickly found the formula and got the so passionately desired Accepted.

However, the professor wasn't very much impressed. He decided that the problem represented on Timmy's Online Judge was very dull and simple: it only had three possible colors of flag stripes and only two limitations. He suggested a complicated task to Igor K. and the fellow failed to solve it. Of course, we won't tell anybody that the professor couldn't solve it as well.

And how about you? Can you solve the problem?

The flags consist of one or several parallel stripes of similar width. The stripes can be one of the following colors: white, black, red or yellow. You should find the number of different flags with the number of stripes from L to R, if:

• a flag cannot have adjacent stripes of one color;
• a flag cannot have adjacent white and yellow stripes;
• a flag cannot have adjacent red and black stripes;
• a flag cannot have the combination of black, white and red stripes following one after another in this or reverse order;
• symmetrical flags (as, for example, a WB and a BW flag, where W and B stand for the white and black colors) are considered the same.

当伊戈尔·K 还是一名大一新生时，他的教授曾严格要求他以及其他所有大一新生参加编程竞赛。某天，一个名为“旗帜”（Flags）的问题吸引了他的注意，该题出自一个名为蒂米在线评测系统（Timmy's Online Judge）的网站。题目要求计算满足特定条件的三色旗帜的数量……实际上，这并不重要。伊戈尔·K 很快推导出了公式，并成功获得了梦寐以求的 “Accepted”（通过）结果。

然而，教授对此印象并不深刻。他认为蒂米在线评测系统上所呈现的这道题十分枯燥且简单：它仅涉及三种可能的条纹颜色，且仅有两条限制条件。于是，教授向伊戈尔·K 提出了一道更复杂的题目，而后者未能解出。当然，我们不会告诉任何人——其实教授本人也没能解出这道题。

那么，你呢？你能解决这个问题吗？

旗帜由一条或多条宽度相同的平行条纹构成。每条条纹的颜色只能是以下四种之一：白色（white）、黑色（black）、红色（red）或黄色（yellow）。你需要计算条纹数目在 $L$ 到 $R$（含端点）之间的不同旗帜的总数，要求满足：

• 旗帜中不能出现相邻的同色条纹；
• 旗帜中不能出现相邻的白色与黄色条纹；
• 旗帜中不能出现相邻的红色与黑色条纹；
• 旗帜中不能出现黑色、白色、红色条纹按此顺序或其逆序（即红、白、黑）连续出现；
• 对称的旗帜（例如，WB 旗与 BW 旗，其中 W 和 B 分别代表白色和黑色）被视为同一种旗帜。

The only line contains two integers L and R (1 ≤ L ≤ R ≤ 109). They are the lower and upper borders of the number of stripes on the flag.

唯一一行包含两个整数 $L$ 和 $R$（$1 \le L \le R \le 10^9$）。它们分别表示国旗条纹数量的下界与上界。

Print a single number — the number of different flags that would satisfy the condition of the problem and would have from L to R stripes, modulo 1000000007.

输出一个整数——满足题目条件且条纹数量在 $L$ 到 $R$ 之间的不同旗帜的数量，对 $1000000007$ 取模。

In the first test the following flags exist (they are listed in the lexicographical order, the letters B, R, W, Y stand for Black, Red, White and Yellow correspondingly):

3 stripes: BWB, BYB, BYR, RWR, RYR, WBW, WBY, WRW, WRY, YBY, YRY (overall 11 flags).

4 stripes: BWBW, BWBY, BYBW, BYBY, BYRW, BYRY, RWRW, RWRY, RYBW, RYBY, RYRW, RYRY (12 flags).

That's why the answer to test 1 is equal to 11 + 12 = 23.

在第一个测试用例中，存在以下旗帜（按字典序排列，其中字母 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$。