블록 3

여러 가지 블록으로 직사각형을 빈틈없이 채우려고 한다. $1 \times N$ 블록, $2 \times N$ 블록, ..., $N \times N$ 블록이 종류마다 무한히 있다.

이 블록으로 세로가 $N$이고 가로가 $M$인 직사각형을 채운다. 블록끼리 겹칠 수 없고 직사각형 밖으로 나갈 수도 없다. 블록은 90도 돌려서 놓을 수 있다. 즉 $k \times N$ 블록은 세로 $k$ 가로 $N$으로 놓을 수도 있고, 세로 $N$ 가로 $k$로 놓을 수도 있다.

채우는 방법이 모두 몇 가지인지 세어 1999로 나눈 나머지를 구하여라. 어느 한 칸이라도 덮는 블록의 놓인 자리가 다르면 서로 다른 방법이다.

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

첫째 줄에 채우는 방법의 수를 1999로 나눈 나머지를 출력한다.