Blocks 3

You fill a rectangle completely with blocks. For each of the $1 \times N$, $2 \times N$, ..., $N \times N$ blocks you have an unlimited supply.

Fill a rectangle of height $N$ and width $M$ with these blocks. Blocks must not overlap and must not stick out of the rectangle. A block may be rotated by 90 degrees, so a $k \times N$ block can be placed as $k$ rows by $N$ columns, or as $N$ rows by $k$ columns.

Count the ways to fill the rectangle and print that count modulo 1999. Two ways are different when at least one cell is covered by a block sitting in a different place.

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

Print the number of ways to fill the rectangle, modulo 1999.