染色

【问题描述】
最近大大很happy,她制作了一些小旗,小旗都排成一列。现在她有四种颜色,分别为R,B,W,Y。突发奇想的大大决定出个问题考考你。她想知道,n面小旗染色有多少种不同的方案数。这样太简单了,答案不就是4^n么。于是她加了点限制,有5个限制条件,分别要求
1、相邻两面旗染色不相同
2、R,B两种颜色不能相邻
3、Y,W两种颜色不能相邻
4、R,W,B不能在一起。即不能出现连续三个是RWB的排列。
5、正反一样的算一种
但是大大觉得这样还是太简单了,于是她定义f(n)为n面红旗的方案数,她给你L和R两个正整数,让你计算∑Ri=Lf(i)∑i=LRf(i),但是由于答案太大,你只需要mod 1000000007即可。
求答案。

【输入格式】
共一行两个正整数L和R,保证L<=R。

【输出格式】
输出只有一行,一个整数。

【样例输入1】
3 4
【样例输出1】
23
对于样例一的解释:
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 种)。
所以答案为11+12=23种。

【样例输入2】
5 6
【样例输出2】
64

【数据范围】
对于10%的数据,有1<=L<=R<=10
另有40%的数据,有 R-L+1<=10
对于100%的数据,1<=L<=R <=1000000000