Filling a rectangle with blocks

Time limit1sMemory limit256 MB

Summary

Count the ways to tile an N by M rectangle with rectangles of size k by N for any k, each rotatable, modulo 1999.

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

Problem

You have an unlimited number of blocks of each size $1 \times N$ , $2 \times N$ , $\dots$ , $N \times N$ . Use them to fill a rectangle of $N$ rows and $M$ columns with no gaps.

A block can be turned by $90^\circ$ . That is, a $k \times N$ block can be placed as $k$ rows by $N$ columns, or as $N$ rows by $k$ columns. Blocks must not overlap and must not stick out of the rectangle.

Two fillings count as different if any cell is covered by a block of a different position or shape. Print the number of fillings modulo $1999$ .

Input

The first line contains $N$ and $M$ , separated by a space. ( $1 \le N \le 100$ , $1 \le M \le 10^4$ )

Output

Print the number of fillings modulo $1999$ on one line.

Examples1

Example 1
Input
```
2 12
```
Expected output
```
732
```