서로 다른 합

우리는 참가자들이 복면산을 푸는, Google Code Jam 2010을 위한 멋진 문제를 생각해 냈다. 하지만 이 문제의 테스트 케이스를 만드는 데 여러분의 도움이 필요하다. 더 정확히 말하면, 복면산으로 변환하기에 충분히 좋은(아래에서 정의하는 의미에서) 덧셈 등식에 관심이 있다.

이 문제를 풀기 위해 복면산이 무엇인지 알 필요는 없다. 필요한 모든 정의를 제공할 것이기 때문이다. 복면산 등식은 모든 피가수(더해지는 수)와 합이 다음과 같이 동일한 오른쪽 경계에 맞춰지도록 작성된 덧셈 등식으로 정의한다.

124
 31
 25
---
180

또한 복면산 등식의 각 열에서 그 열에 있는 모든 피가수의 숫자는 서로 달라야 한다. 이 제약에는 합을 포함하지 않는다는 점에 유의하라. 예를 들어 위 등식에서 첫 번째 열에는 숫자 1만 있고, 두 번째 열에는 숫자 2,3, 2이 있으며, 세 번째 열에는 숫자 4, 1, 5이 있다. 이 등식은 두 번째 열에 2가 두 개 있으므로 복면산 등식이 아니다. 하지만 마지막 피가수를 15로 바꾸고 합을 170로 바꾸면 복면산 등식이 된다.

복면산 등식의 피가수는 항상 양수이며 선행 영 없이 작성된다는 점에 유의하라. 피가수의 순서는 중요하지 않다(즉, 피가수의 순서만 다른 두 등식은 같은 것으로 간주한다).

위 예제는 10진법이었지만, 다른 진법의 복면산 등식에도 관심이 있다. b진법에서 "digit"는 0부터 b-1까지의 어떤 정수도 의미할 수 있다는 점에 유의하라. 다음은 23진법의 복면산 등식이다.

I7B
 JJJ
----
1F47

이 예제에서 "I"는 숫자 18을, "B"는 숫자 11를, "J"는 숫자 19를, "F"는 숫자 15을 나타낸다. 십진 표기법으로 두 피가수는 18*$23^{2}$ + 723 + 11 = 9694와 19$23^{2}$ + 1923 + 19 = 10507이고, 합은 1$23^{3}$ + 15*$23^{2}$ + 4*23 + 7 = 20201이다. 10 이상의 숫자를 문자로 나타낸 것은 오직 예제를 명확하게 보이기 위한 것이라는 점에 유의하라. 이 문제에서는 그러한 숫자를 글로 정확히 어떻게 표기하는지는 실제로 중요하지 않다.

주어진 진법 B에서 합이 N인 복면산 등식은 몇 개인가?

답이 매우 클 수 있으므로 1000000007로 나눈 나머지를 출력한다.

제한

메모리 제한: 1GB. 1 ≤ T ≤ 20.

작은 데이터 세트 (테스트 세트 1 - 공개)

시간 제한: 30초. 1 ≤ N ≤ 100. 2 ≤ B ≤ 10.

큰 데이터 세트 (테스트 세트 2 - 비공개)

시간 제한: 120초. 1 ≤ N ≤ $10^{18}$. 2 ≤ B ≤ 70.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어진다. 각 줄에는 두 양의 정수 N과 B가 주어진다. 모든 입력 수는 10진법으로 주어진다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 케이스 번호이고, y는 주어진 합을 갖는 서로 다른 복면산 등식의 개수이다. 이 수는 매우 클 수 있으므로 1000000007로 나눈 나머지를 출력한다. 물론 출력 자체는 10진법이어야 한다.

설명

합이 6인 4개의 복면산 등식은 다음과 같다.

그리고 4진법에서 합이 8=20_{4}인 4개의 복면산 등식은 다음과 같다.