3996: 染色问题 color

内存限制:128 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:0 通过:0

题目描述

现在有n个旗子拍成一排,用4种颜色R、B、W、Y染色,满足以下条件下:
1.相邻旗子不能同色
2.R、B两种颜色不能相邻
3.Y、W两种颜色不能相邻
4.R、W、B不能在一起(不能出现连续三个是RWB的排列,即RWB、WBR等等)
5.正反一样算一种
染色方案数为f(n)
现在给出L、R求出 L<=i<=R ∑f(i)
答案mod 1e9+7

输入格式

第一行两个正整数L、R
1<=L<=R<=10^9

输出格式

一行一个整数表示答案。

输入样例 复制

3 4

输出样例 复制

23