CF93D Flags

当 Igor K. 还是新生时，他的教授严厉地要求他和所有其他新生一起参加程序设计奥林匹克竞赛。一天，他在一个叫 Timmy's Online Judge 的网站上注意到了一道叫做 “Flags” 的题目。在这道题中，需要找出满足某些条件的三色旗的数量……其实具体条件是什么并不重要。Igor K. 很快找到了公式，并如愿以偿地得到了 Accepted。 然而，教授却并不怎么满意。他认为 Timmy's Online Judge 上的那道题太无聊、太简单——只涉及旗帜条纹的三种颜色和两个限制。于是，他给 Igor K. 出了一道更复杂的题目，但 Igor K. 没能解出来。当然，我们不会告诉任何人，其实教授自己也解不出来。 那么你呢？你能解决这道题吗？ 每面旗帜由一条或多条平行的，宽度相同的条纹组成。条纹可以是以下颜色之一：白色、黑色、红色或黄色。你需要计算出旗帜条纹数从 $L$ 到 $R$ 的所有不同种类旗帜的数量，要求： - 旗帜不能有相邻的相同颜色条纹； - 旗帜不能有相邻的白色和黄色条纹； - 旗帜不能有相邻的红色和黑色条纹； - 旗帜不能有连续出现（正向或逆向）黑色、白色和红色的组合； - 对称的旗帜（例如 WB 和 BW，W 表示白色，B 表示黑色）被认为是相同的。

输入仅一行，包含两个整数 $L$ 和 $R$（$1 \leq L \leq R \leq 10^{9}$），表示旗帜条纹数的下限和上限。

输出一个整数，表示满足条件的具有 $L$ 到 $R$ 条纹数的不同旗帜的数量，对 $1000000007$ 取模。

在第一个测试样例中，存在如下旗帜（按字典序排列，B 表示黑色，R 表示红色，W 表示白色，Y 表示黄色）： 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 种）。 所以样例 1 的答案为 $11+12=23$。 由 ChatGPT 5 翻译