Blocks 3

Time limit1sMemory limit256 MB

Summary

Count the tilings of an N by M rectangle using blocks of size k by N for any k, allowing 90-degree rotation, modulo 1999.

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

Problem

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.

Input

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

Output

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

Examples4

Example 1
Input
```
2 12
```
Expected output
```
732
```
Example 2
Input
```
1 1
```
Expected output
```
1
```
Example 3
Input
```
3 3
```
Expected output
```
7
```
Example 4
Input
```
5 5
```
Expected output
```
31
```