← 返回题目列表

Codeforces · 93/D

D. 标志

中文机器翻译题面 查看原题

当 Igor K. 还是一名新生时,他的教授严格要求他以及所有其他新生解决编程奥林匹克竞赛。有一天,一个名为 Timmy's Online Judge 的网站上的一个名为“Flags”的问题引起了他的注意。在这个问题中,我们必须找到满足条件的三色旗的数量……实际上,这并不重要。 Igor K. 很快找到了公式并获得了如此热切的期望。

然而,教授并没有留下太深刻的印象。他认为 Timmy's Online Judge 上呈现的问题非常枯燥和简单:它只有三种可能的旗帜条纹颜色,并且只有两个限制。他向 Igor K. 提出了一项复杂的任务,但后者未能解决。当然,我们不会告诉任何人教授也解决不了这个问题。

你呢?你能解决问题吗?

标志由一条或多条宽度相似的平行条纹组成。条纹可以是以下颜色之一:白色、黑色、红色或黄色。您应该找到不同标志的数量以及从 L 到 R 的条纹数量,如果:

- 旗帜不能有一种颜色的相邻条纹;
- 旗帜不能有相邻的白色和黄色条纹;
- 旗帜不能有相邻的红色和黑色条纹;
- 旗帜不能具有按此顺序或相反顺序依次排列的黑色、白色和红色条纹的组合;
- 对称标志(例如 WB 和 BW 标志,其中 W 和 B 代表白色和黑色)被认为是相同的。

输入

唯一一行包含两个整数 L 和 R (1 ≤ L ≤ R ≤ 109)。它们是旗帜上条纹数量的下边界和上边界。

输出

打印一个数字 — 满足问题条件并且具有从 L 到 R 条纹的不同标志的数量,以 1000000007 为模。

示例

输入 #1

3 4

输出 #1

23

输入 #2

5 6

输出 #2

64

注意

在第一个测试中存在以下标志(它们按字典顺序列出,字母 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。