CF295D Greg and Caves
题目描述
Greg 有一个 8868,其屏幕为一 $n \times m$ 的矩形,每个像素可以是黑色或白色。我们考虑将 8868 的行从上到下编号为 $1$ 到 $n$。类似地,8868 的列从左到右编号为 $1$ 到 $m$。
Greg 认为 8868 显示一个洞时,当且仅当以下情况:
- $\exist$ 区间 $[l,r](1 \leq l \leq r \leq n)$,使得每一行恰有两个黑色像素,而所有其他行只有白色像素;
- $\exist$ 行 $t(l \leq t \leq r)$,使得对于 $\forall(i,j)(l \leq i \leq j \leq t)$,第 $i$ 行中黑色单元格之间列的集合 $S_1$,与第 $j$ 行中黑色单元格之间列的集合 $S_2$,满足 $S_1 \subseteq S_2$,同样对于 $\forall (i,j)(t \leq i \leq j \leq r)$,第 $i$ 行中黑色单元格之间列的集合 $S_1$,与第 $j$ 行中黑色单元格之间列的集合 $S_2$,满足 $S_2 \subseteq S_1$,
Greg 想知道,有多少种方案能让他的 8868 显示一个洞。当且仅当两个屏幕存在一个位置像素颜色不同,两种方案不同。
帮帮 Greg 吧!
输入格式
一行两个整数 $n$,$m$ 表示 8868 的分辨率。
输出格式
一行,答案在模 $10^9+7$ 意义下的值。
说明/提示
对于全部数据,$1 \leq n,m \leq 2000$。