블록으로 직사각형 채우기

$1 \times N$, $2 \times N$, $\dots$, $N \times N$ 크기의 블록이 종류마다 무한히 있다. 이 블록으로 $N$행 $M$열 직사각형을 빈틈없이 채우려고 한다.

블록은 $90^\circ$ 돌려서 놓을 수 있다. 즉 $k \times N$ 블록은 $k$행 $N$열로 놓을 수도 있고 $N$행 $k$열로 놓을 수도 있다. 블록끼리 겹치거나 직사각형 밖으로 나가면 안 된다.

어떤 칸을 덮는 블록의 위치나 모양이 한 군데라도 다르면 서로 다른 방법으로 센다. 채우는 방법의 수를 $1999$로 나눈 나머지를 구하여라.

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

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