각 자리가 서로 다른 덧셈식

모든 덧셈 항과 합을 오른쪽 끝에 맞춰 적은 덧셈식을 복면산 덧셈식이라고 하자. 다음이 그 예다.

124
 31
 25
---
180

덧셈 항은 앞에 0을 붙이지 않고 적은 양의 정수다. 각 열에서 그 열에 놓인 덧셈 항의 숫자는 모두 서로 달라야 한다. 합의 숫자는 이 조건에 넣지 않는다. 위 식의 첫째 열에는 1만 있고, 둘째 열에는 2, 3, 2가 있으며, 셋째 열에는 4, 1, 5가 있다. 둘째 열에 2가 두 번 나오므로 위 식은 복면산 덧셈식이 아니다. 마지막 덧셈 항을 15로 바꾸고 합을 170으로 바꾸면 복면산 덧셈식이 된다.

덧셈 항의 순서는 상관없다. 덧셈 항의 순서만 다른 두 식은 같은 식으로 센다.

밑이 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 100$
• $2 \le B \le 10$

각 테스트 케이스마다 한 줄에 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이고 합이 $20_4 = 8$인 복면산 덧셈식도 네 개다.

20
--
20

11
 3
--
20

13
 1
--
20

10
 3
 1
--
20