블록 4

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

요약

1부터 N까지의 k에 대해 k×N 블록(회전 가능)을 사용해 N×M 직사각형을 채우는 경우의 수를 1999로 나눈 나머지를 구한다. M은 최대 10^10이다.

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

문제

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

예제2

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