3631.Greg and Caves

Time Limit: 1s Memory Limit: 256MB

Greg has a pad. The pad's screen is an n \times 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 \le l \le r \le 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 \le t \le r), such that for all pairs of rows with numbers i and j (l \le i \le j \le 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 \le i \le j \le 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.

Input Format(From the terminal/stdin)

The first line contains two integers n, m - the pad's screen size (1 \le n,m \le 2000).

Output Format(To the terminal/stdout)

In the single line print the remainder after dividing the answer to the problem by 1000000007 (109+7).

Sample Input 1

Copy
1 1
 · \n

Sample Output 1

Copy
0
 \n

Sample Input 2

Copy
4 4
 · \n

Sample Output 2

Copy
485
   \n

Sample Input 3

Copy
3 5
 · \n

Sample Output 3

Copy
451
   \n

Submit

请先 登录

© 2025 FAQs