복면산 덧셈식 세기

문제

복면산 덧셈식은 더하는 수와 합을 모두 오른쪽 끝에 맞춰 세로로 쓴 덧셈식이다. 예를 들면 다음과 같다.

여기에 더해, 각 열에 놓인 더하는 수의 숫자는 모두 서로 달라야 한다. 합은 이 조건에 들어가지 않는다. 위 식에서 첫째 열에는 숫자 1만 있고, 둘째 열에는 2와 3과 2가, 셋째 열에는 4와 1과 5가 있다. 둘째 열에 2가 두 번 나오므로 위 식은 복면산 덧셈식이 아니다. 마지막 더하는 수를 15로, 합을 170으로 바꾸면 복면산 덧셈식이 된다.

더하는 수는 항상 양수이고 앞자리에 0을 붙이지 않는다. 자릿수가 짧은 수는 자기 길이를 넘어가는 열에 아무 숫자도 놓지 않는다. 더하는 수의 순서는 상관없다. 순서만 다른 두 식은 같은 식으로 센다.

10 이외의 진법도 쓸 수 있다. $B$ 진법의 숫자는 $0$ 이상 $B-1$ 이하의 정수를 뜻한다. 다음은 23진법 복면산 덧셈식이다.

 I7B
 JJJ
----
1F47

여기서 "I"는 숫자 18, "B"는 11, "J"는 19, "F"는 15를 나타낸다. 10진법으로 옮기면 더하는 두 수는 $18 \times 23^2 + 7 \times 23 + 11 = 9694$ 와 $19 \times 23^2 + 19 \times 23 + 19 = 10507$ 이고, 합은 $1 \times 23^3 + 15 \times 23^2 + 4 \times 23 + 7 = 20201$ 이다. 10 이상인 숫자를 문자로 적은 것은 예시를 읽기 쉽게 하려는 것일 뿐이고, 그런 숫자를 어떤 기호로 적는지는 이 문제에서 상관없다.

$B$ 진법에서 합이 $N$ 인 복면산 덧셈식이 몇 개인지 세어라. 답이 매우 클 수 있으므로 $1000000007$ 로 나눈 나머지를 출력한다.

입력

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

제한

$1 \le T \le 20$
$1 \le N \le 10^{18}$
$2 \le B \le 70$

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 $B$ 진법에서 합이 주어진 $N$ 인 복면산 덧셈식의 개수를 $1000000007$ 로 나눈 나머지이다. y는 10진법으로 출력한다.

힌트

10진법에서 합이 6인 복면산 덧셈식은 네 개다. $6 = 6$ , $1 + 5 = 6$ , $2 + 4 = 6$ , $1 + 2 + 3 = 6$ 이다.

4진법에서 합이 $8 = 20_4$ 인 식도 네 개다.

20
--
20