Blocks 2

Count the ways to tile an N x M rectangle with rotated k x N blocks (k=1..N), modulo 1999, where M can be as large as 10^10.

Hard9CombinatoricsDynamic programmingMatrixNumber theoryNo attempts yetTime limit1sMemory limit256 MB

Description

Examples2

Problem

You have an unlimited supply of blocks of each size $1 \times N$ , $2 \times N$ , ..., $N \times N$ . A block may be rotated by 90 degrees before you place it. Blocks must not overlap and must not stick out of the rectangle.

Count the ways to fill an $N \times M$ rectangle completely with these blocks, and report that count modulo 1999. Blocks of the same size are interchangeable, so two fillings that cover the rectangle with the same shapes in the same places count as one way.

Input

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

Output

Print the number of ways to fill the $N \times M$ rectangle, modulo 1999, on one line.