15572번 - 블록 4

여러 가지 블록들을 이용하여 직사각형 모양을 만들려고 한다. 우리에게는 1 × N 블록, 2 × N 블록, ..., N × N 블록이 무한하게 있다. 이 블록들을 사용하여 N × M 모양을 만들고 싶다. 만들 수 있는 총 방법의 수를 1999로 나눈 나머지를 구하여라.

첫 번째 줄에 N과 M이 입력된다. (1 ≤ N ≤ 10³, 1 ≤ M ≤ 10¹⁰)

총 가능한 경우의 수를 1999로 나눈 나머지를 출력한다.