2630: 例6.1-2 染色
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
最近小x很happy，她制作了一些小旗，小旗都排成一列。现在她有四种颜色分别为R、B、W、Y。突发奇想的小x决定出个问题考考你。她想知道，n面小旗染色有多少种不同的方案数。这样太简单了，答案不就是4n吗!于是，她加了5个限制条件，分别要求：
1．相邻两面旗染色不相同；
2．R，B两种颜色不能相邻；
3．Y，W两种颜色不能相邻；
4．R，W，B不能在一起。即不能出现连续三个是RWB的排列；
5．正反一样的算一种。
但是，小x觉得这样还是太简单了，于是她定义f（n）为n面红旗的方案数，她给你L和R两个正整数，让你计算以下式子：
由于答案太大，你只需要mod 1000000007即可。
输入
输入文件一行两个正整数L和R，保证L≤R。
输出
输出文件只有一行一个整数。
样例输入 复制
3 4样例输出 复制
23
【解释样例】
对于样例1的解释：
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种。
【数据范围】
对于10%的数据满足：1≤L≤R≤10；
另有40%的数据满足：R-L+1≤10；
对于100%的数据满足：1≤L≤R≤109。提示
【解释样例】
对于样例1的解释：
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种。
【数据范围】
对于10%的数据满足：1≤L≤R≤10；
另有40%的数据满足：R-L+1≤10；
对于100%的数据满足：1≤L≤R≤109。