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