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的分辨率$(1 \leq n,m \leq 2000)$ #### 输出格式： 一行，答案在模$1e9+7$意义下的数值

Greg has a pad. The pad's screen is an $ n×m $ rectangle, each cell can be either black or white. We'll consider the pad rows to be numbered with integers from 1 to $ n $ from top to bottom. Similarly, the pad's columns are numbered with integers from 1 to $ m $ from left to right. Greg thinks that the pad's screen displays a cave if the following conditions hold: - There is a segment $ [l,r] $ $ (1<=l<=r<=n) $ , such that each of the rows $ l,l+1,...,r $ has exactly two black cells and all other rows have only white cells. - There is a row number $ t $ $ (l<=t<=r) $ , such that for all pairs of rows with numbers $ i $ and $ j $ $ (l<=i<=j<=t) $ the set of columns between the black cells in row $ i $ (with the columns where is these black cells) is the subset of the set of columns between the black cells in row $ j $ (with the columns where is these black cells). Similarly, for all pairs of rows with numbers $ i $ and $ j $ $ (t<=i<=j<=r) $ the set of columns between the black cells in row $ j $ (with the columns where is these black cells) is the subset of the set of columns between the black cells in row $ i $ (with the columns where is these black cells). Greg wondered, how many ways there are to paint a cave on his pad. Two ways can be considered distinct if there is a cell that has distinct colors on the two pictures. Help Greg.

The first line contains two integers $ n $ , $ m $ — the pad's screen size $ (1<=n,m<=2000) $ .

In the single line print the remainder after dividing the answer to the problem by $ 1000000007 $ $ (10^{9}+7) $ .

1 1

0

4 4

485

3 5

451