题目描述

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

1. 相邻两面旗染色不相同；
2. $\tt R,B$ 两种颜色不能相邻；
3. $\tt Y,W$ 两种颜色不能相邻；
4. $\tt R,W,B$ 不能在一起。即不能出现连续三个是 $\tt RWB$ 的排列；
5. 正反一样的算一种。

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

由于答案太大，你只需要 $\mod 10^9+7$ 即可。

输入格式

一行两个正整数 $L$ 和 $R$，保证 $L≤R$。

输出格式

一行一个整数表示答案。

3 4

23

$3$ 面小旗：$\tt BWB$，$\tt BYB$，$\tt BYR$，$\tt RWR$，$\tt RYR$，$\tt WBW$，$\tt WBY$，$\tt WRW$，$\tt WRY$，$\tt YBY$，$\tt YRY$，$11$ 种。

$4$ 面小旗：$\tt BWBW$，$\tt BWBY$，$\tt BYBW$，$\tt BYBY$，$\tt BYRW$，$\tt BYRY$，$\tt RWRW$，$\tt RWRY$，$\tt RYBW$，$\tt RYBY$，$\tt RYRW$，$\tt RYRY$，$12$ 种。

所以答案为 $11+12=23$ 种。

5 6

64

数据范围/提示

对于 $10\%$ 的数据满足：$1≤L≤R\le10$；

另有 $40\%$ 的数据满足：$R-L+1≤10$；

对于 $100\%$ 的数据满足：$1≤L≤R\le10^9$。