← 返回题目列表

Codeforces · 1239/A

A. 傻瓜伊凡和概率论

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

最近愚人伊万决定变得更聪明,学习概率论。他认为他对这个学科相当了解,因此他开始表现得好像他已经获得了该领域的博士学位。

为了证明他的技能,Ivan 决定向他的朋友们展示随机图片的概念。图片是由 $$$n$$$ 行和 $$$m$$$ 列组成的字段,其中每个单元格都是黑色或白色。如果对于每个单元格最多有一个相同颜色的相邻单元格,则伊万称该图片是随机的。如果两个单元共用一条边,则认为它们是相邻的。

Ivan 的兄弟花了一些时间试图解释随机性通常不是这样运作的。为了说服伊万,他们想计算不同的随机(根据伊万)图片的数量。如果两张图片上至少有一个单元格的颜色不同,则认为这两张图片不同。由于此类图片的数量可能相当大,因此将其以 $$$10^9 + 7$$$ 为模打印。

输入

唯一一行包含两个整数$$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 100\,000$$$),即字段的行数和列数。

输出

打印一个整数,随机图片的数量以 $$$10^9 + 7$$$ 为模。

示例

输入 #1

2 3

输出 #1

8

注意

下图显示了大小为$$$2$$$×$$$3$$$的所有可能的随机图片。