블록 3

시간 제한1초메모리 제한256 MB

요약

k×N (k는 1부터 N) 크기의 블록을 90도 회전도 허용해 N×M 직사각형에 겹치지 않게 채우는 방법의 수를 1999로 나눈 나머지를 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 조합론, 수학, 행렬
정답자: 아직 제출이 없습니다

문제

여러 가지 블록으로 직사각형을 빈틈없이 채우려고 한다. $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로 나눈 나머지를 출력한다.

예제4

예제 1
입력
```
2 12
```
예상 출력
```
732
```
예제 2
입력
```
1 1
```
예상 출력
```
1
```
예제 3
입력
```
3 3
```
예상 출력
```
7
```
예제 4
입력
```
5 5
```
예상 출력
```
31
```