问题描述

最近小x很happy，她制作了一些小旗，小旗都排成一列。现在她有四种颜色分别为R、B、W、Y。突发奇想的小x决定出个问题考考你。她想知道，n面小旗染色有多少种不同的方案数。这样太简单了，答案不就是$4^n$吗!于是，她加了5个限制条件，分别要求：

• 相邻两面旗染色不相同；
• R，B两种颜色不能相邻；
• Y，W两种颜色不能相邻；
• R，W，B不能在一起。即不能出现连续三个是RWB的排列；
• 正反一样的算一种。

但是，小x觉得这样还是太简单了，于是她定义f(n)为n面红旗的方案数，她给你L和R两个正整数，让你计算以下式子：

$\displaystyle\sum_{i=L}^{R}f(i)$

由于答案太大，你只需要mod 1000000007即可。

输入格式

输入文件一行两个正整数L和R，保证L≤R。

输出格式

输出文件只有一行一个整数。

样例

3 4

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种。

样例

5 6

64

数据范围

• 对于10%的数据满足：$1≤L≤R≤10$
• 另有40%的数据满足：$R-L+1≤10$
• 对于100%的数据满足：$1≤L≤R≤10​^9$

来源

• 信息学奥赛之数学一本通
• stong9070整理