블록 4

여러 크기의 블록으로 직사각형을 채우려고 한다. $1 \times N$ 블록, $2 \times N$ 블록, ..., $N \times N$ 블록이 각각 무한히 많다. 블록은 90도 돌려서 놓아도 된다. 즉 $k \times N$ 블록은 세로 $k$ 칸 가로 $N$ 칸으로 놓을 수도 있고, 세로 $N$ 칸 가로 $k$ 칸으로 놓을 수도 있다.

이 블록으로 세로 $N$ 칸, 가로 $M$ 칸인 직사각형을 빈틈없이 겹치지 않게 채우는 방법의 수를 구하여라. 크기가 같은 블록은 서로 구분하지 않으므로, 채운 모양이 같으면 같은 방법이다. 답이 매우 커질 수 있으니 $1999$로 나눈 나머지를 출력한다.

첫째 줄에 $N$과 $M$이 공백 하나를 사이에 두고 주어진다. ($1 \le N \le 10^3$, $1 \le M \le 10^{10}$)

첫째 줄에 직사각형을 채우는 방법의 수를 $1999$로 나눈 나머지를 출력한다.