Blocks 4

You want to fill a rectangle with blocks of several sizes. You have an unlimited supply of $1 \times N$ blocks, $2 \times N$ blocks, ..., $N \times N$ blocks. A block may be turned 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 a rectangle of $N$ rows and $M$ columns with no gap and no overlap. Blocks of the same size are not distinguished, so two fillings are the same when the filled shape is the same. The count grows large, so print it modulo $1999$.

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

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