← 返回题目列表

Codeforces · 295/D

D. 格雷格和洞穴

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

格雷格有一个垫子。 pad 的屏幕是一个 n × m 的矩形,每个单元格可以是黑色或白色。我们将考虑将焊盘行从上到下用 1 到 n 的整数进行编号。类似地,pad 的列从左到右用 1 到 m 的整数进行编号。

Greg 认为如果满足以下条件,则平板电脑的屏幕会显示洞穴:

- 有一个段 [l, r] (1 ≤ l ≤ r ≤ n),使得每行 l, l + 1, ..., r 恰好有两个黑色单元格,而所有其他行只有白色单元格。
- 存在一个行号 t (l ≤ t ≤ r),使得对于编号为 i 和 j 的所有行对 (l ≤ i ≤ j ≤ t),第 i 行中黑色单元格之间的列集(以及这些黑色单元格所在的列)是第 j 行中黑色单元格之间的列集的子集(其中这些黑色单元格在哪里)。类似地,对于编号为 i 和 j 的所有行对 (t ≤ i ≤ j ≤ r),第 j 行中黑色单元格之间的列集(这些黑色单元格所在的列)是第 i 行中黑色单元格之间的列集(这些黑色单元格所在的列)的子集。

格雷格想知道,有多少种方法可以在他的垫子上画一个洞穴。如果有一个单元格在两张图片上具有不同的颜色,则可以认为两种方式是不同的。

帮助格雷格。

输入

第一行包含两个整数 n、m — 键盘的屏幕尺寸 (1 ≤ n, m ≤ 2000)。

输出

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

示例

输入 #1

1 1

输出 #1

0

输入 #2

4 4

输出 #2

485

输入 #3

3 5

输出 #3

451