The Fortress Defense

Time limit2sMemory limit1024 MB

Summary

Count every way to nest non-touching rectangle contours inside an h by w grid and sum the defense levels over all configurations, modulo 1e9+7.

Level: Medium7 of 10
Topics: Combinatorics, Dynamic programming, Math
Solved: No attempts yet

Problem

The Flatlanders are building a fortress on a grid of square cells. The fortress has several contours of defense. Each contour is a rectangle with sides along the borders of the cells.

The first, outer, defense contour is a rectangle of size $h \times w$ . Each next contour lies strictly inside all previous ones. Defense contours must not share any points.

The defense level of a cell is the number of defense contours inside which the cell lies. The defense level of a fortress is the sum of the defense levels of all its cells. For example, the fortress in the picture has defense level $16 \cdot 1 + 8 \cdot 2 + 3 = 35$ .

The Flatlanders want to know every possible way to build a fortress. For each way, they compute the defense level, then sum these values over all ways. Help them compute this sum. The answer can be large, so output it modulo $10^9 + 7$ .

Input

The first line of input contains two integers $h$ and $w$ ( $1 \le h, w \le 400$ ).

Output

Output a single integer: the sum of defense levels for all ways, modulo $10^9 + 7$ .

Hint

All possible ways to build a fortress from the first sample are in the picture.

All possible ways to build a fortress from the second sample are in the picture.

Examples2

Example 1
Input
```
3 3
```
Expected output
```
19
```
Example 2
Input
```
5 5
```
Expected output
```
1060
```