← 返回题目列表

Codeforces · 273/D

D. 迪玛和图

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

Dima 喜欢在一张方格纸上制作图片。迪马更喜欢那些描绘他最喜欢的人物之一的照片。

一张大小为 n × m 的方格纸由一个表格表示,该表格由 n 行和 m 列组成。空白方格纸上的所有方块都是白色的。迪马将图片定义为一张白纸上的图像,通过将一些方块涂成黑色而获得。

如果满足以下条件,图片描绘的是迪马最喜欢的人物之一:

- 图片至少包含一个绘制的单元格;
- 所有绘制的单元格形成一个连通集,也就是说,您可以从任何一个绘制的单元格到达任何其他一个(您可以从一个单元格移动到一侧相邻的单元格);
- 从坐标 (x1, y1) 处的绘制单元到坐标 (x2, y2) 处的绘制单元(仅穿过彩色单元)所需的最小移动次数,等于 |x1 - x2| + |y1 - y2|。

现在迪马想知道:一张 n × m 的纸上有多少幅画,描绘了他最喜欢的人物之一?以 1000000007 (109 + 7) 为模计算此数字。

输入

第一行包含两个整数 n 和 m — 这张纸的尺寸 (1 ≤ n, m ≤ 150)。

输出

在一行中打印问题答案除以数字 1000000007 (109 + 7) 后的余数。

示例

输入 #1

2 2

输出 #1

13

输入 #2

3 4

输出 #2

571