트리솔인

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

요약

각 좌표에 매년 양수가 더해지는 k차원 나이 벡터의 수명 기록 중 좌표 합이 n인 벡터에서 끝나는 것의 최대 개수를 7340033으로 나눈 나머지를 구한다.

문제

최근 트리솔 행성의 주민들은 지구인처럼 나이를 정수 하나로 나타내지 않고, k개의 정수로 이루어진 벡터로 나타낸다는 사실이 밝혀졌다. 갓 태어난 트리솔인의 나이 벡터는 k개의 0으로 이루어져 있다. 나이가 들면서 매년 나이 벡터의 각 원소에 어떤 양수가 더해진다.

트리솔인의 삶의 역사란 그가 살아오면서 가졌던 모든 나이 벡터의 집합을 말한다. 지구의 과학자들은 같은 역사를 가진 두 트리솔인은 존재하지 않는다는 것을 알아냈다.

이제 과학자들은 삶의 역사가 원소의 합이 n인 벡터에서 끝나는 트리솔인의 최대 수를 알고 싶어 한다. 이 값을 소수 7340033 = 7·2^20^ + 1로 나눈 나머지를 구하는 프로그램을 작성하시오.

예를 들어 k = 2일 때, 삶의 역사가 합이 5인 벡터에서 끝나는 트리솔인은 8명 존재할 수 있다. 그들의 삶의 역사는 다음과 같다:

(0, 0) - (1, 1) - (2, 3);
(0, 0) - (1, 1) - (3, 2);
(0, 0) - (1, 2) - (2, 3);
(0, 0) - (1, 4);
(0, 0) - (2, 1) - (3, 2);
(0, 0) - (2, 3);
(0, 0) - (3, 2);
(0, 0) - (4, 1).

첫째 줄에 두 정수 n과 k가 주어진다. n은 마지막 나이 벡터의 원소 합이고, k는 벡터의 원소 개수이다 (1 ≤ n ≤ 4239, 1 ≤ k ≤ 10^9).

삶의 역사가 원소의 합이 n인 벡터에서 끝날 수 있는 트리솔인의 최대 수를 출력한다. 답은 7340033 = 7·2^20^ + 1로 나눈 나머지로 출력해야 한다.