| 题目名称 | 1925. [CF 273D]Dima和图像 |
|---|---|
| 输入输出 | dimaandfigure.in/out |
| 难度等级 | ★★ |
| 时间限制 | 3000 ms (3 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cstdio
于2015-04-07加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：1， 提交：1， 通过率：100% | ||||
 cstdio |
100 | 2.556 s | 1.88 MiB | C++ |
| 关于 Dima和图像 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
【题目描述】
Dima喜欢在方格纸上画图，特别地，他有一些格外喜爱的图像。
一张大小为n*m的方格纸是一个有n行m列的表格。在空白方格纸上所有格子都是白色的。把方格纸上一些格子涂黑后就得到了一张“图像”。
Dima喜爱的图像有如下条件：
·图像中包含至少一个黑色格子
·所有黑色格子组成一个四连通集，即，你可以从任意黑色格子到达其他全部黑色格子（你可以从一个格子移动到边相邻的黑格）
·经过黑色格子从任意黑色格子(x1,y1)到黑色格子(x2,y2)所需要的最小移动步数等于|x1-x2|+|y1-y2|。
现在Dima想要知道：有多少种在n*m方格纸上画出他喜爱图像的方案？输出结果模1000000007（10^9+7）的值。
【输入格式】
一行两个正整数n,m，代表方格纸的大小（1<=n,m<=150）.
【输出格式】
一行一个整数，即答案模1000000007（10^9+7）的值。
【样例输入输出】
Input
2 2
Output
13
Input
3 4
Output
571