Blocks 4

Time limit1sMemory limit256 MB

Summary

Count the tilings of an N by M rectangle using blocks of size k by N (rotatable) for k from 1 to N, modulo 1999, where M can be as large as 1e10.

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

Problem

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$ .

Input

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

Output

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

Examples2

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