우측 버튼을 눌러 기기를 연결해주세요.
문제정보
[일반 프로그래밍 문제] 숫자 카드 게임
100


진우는 친구들과 간단한 카드 게임을 하려고 한다. 카드는 총 N장으로 구성되어 있으며 0부터 (N-1) 까지의 정수가 하나씩 적혀져 있다. 이 중 몇 개의 카드를 뽑아 규칙에 맞게 조합을 구성해야 한다. 카드를 뽑는 규칙은 비복원 추출이다. 즉, 같은 카드를 여러 번 뽑을 수는 없다.

카드를 선택하는 규칙은 다음과 같다. 총 N장의 카드 중에서 K장의 카드를 선택해야 한다. 이때 각 카드에 적힌 숫자들을 모두 더한 값을 N으로 나누었을 때 나머지가 0이어야 한다. 

예를 들어서 N=5, K=3인 경우를 생각해보자. [ 0, 1, 2, 3, 4 ]의 카드 뭉치에서 [ 0, 2, 3 ]과 같이 세 장을 선택하면 합은 5가 되고, N으로 나누었을 때 나머지가 0이 된다. 하지만 [ 1, 2, 3 ]과 같이 뽑으면 합은 6이므로 N으로 나누었을 때 나머지가 1이므로 올바르게 선택된 조합이 아니다.

진우는 갑자기 올바른 카드 조합은 총 몇 가지가 있는지 궁금해졌다. 진우의 궁금증을 풀기 위해 두 정수 N, K에 대해 게임의 규칙을 만족하는 조합의 경우의 수를 출력하는 프로그램을 작성하시오.


입력 형식

첫 번째 줄에 두 개의 정수 N, K가 공백으로 구분되어 주어진다.

  • N은 1 이상 1,000 이하의 정수다.
  • K는 1 이상 47 이하의 정수다.


출력 형식

올바른 카드 조합의 총 가짓수를 출력한다.

  • 단, 경우에 따라 숫자가 매우 커질 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.
입/출력 예시
:
공백
:
줄바꿈
:
예시 1
입력
74
출력
5
예시 2
입력
103
출력
12
⋇ 입출력 형식을 잘 지켜주세요