| 题目名称 | 1924. [CF 295D] Greg和洞穴 |
|---|---|
| 输入输出 | gregandcaves.in/out |
| 难度等级 | ★☆ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cstdio
于2015-04-03加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：1， 提交：1， 通过率：100% | ||||
 cstdio |
100 | 1.669 s | 62.00 MiB | C++ |
| 关于 Greg和洞穴 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
这题其实没啥意思，我就来刷个经验……
| ||||
【题目描述】
Greg有一个平板电脑。这个电脑的屏幕是一个n*m的网格，其中每个方格都是黑色或者白色。我们将网格的行从上到下命名为1~n，类似地将列从左到右命名为1~m。
Greg认为平板电脑的屏幕显示出一个洞穴，如果如下两个条件成立：
·有一个区间[l,r]（1<=l<=r<=n），使得第l,l+1,...,r行都恰有两个黑格，而其余行全部是白格。
·存在一行t，使得对于所有的i,j（l<=i<=j<=t），第i行两个黑格之间的格子组成的集合（包括黑格，下同）是第j行两个黑格之间的格子组成的集合的子集。同样地，对于所有的t<=i<=j<=r，第j行两黑格之间格子组成的集合是第i行两黑格之间格子组成集合的子集。
Greg想知道，有多少种在屏幕上显示一个洞穴的方法。两种方法被认为不同，如果在两个图像中某格子的颜色不同。
请帮助Greg。
【输入格式】
一行两个整数n,m，代表格子的大小。（1<=n,m<=2000）
【输出格式】
一行一个正整数，即答案模1000000007（10^9+7）的值。
【样例输入输出】
Input
1 1
Output
0
Input
4 4
Output
485
Input
3 5
Output
451