Chúng tôi đã nghĩ ra một bài toán tuyệt vời cho Google Code Jam 2010 liên quan đến việc các thí sinh giải một phép toán ẩn chữ (cryptarithm). Nhưng chúng tôi cần sự giúp đỡ của bạn trong việc tạo các bộ test cho bài toán; chính xác hơn, chúng tôi quan tâm đến các phương trình cộng đủ tốt (theo nghĩa được định nghĩa dưới đây) để chuyển đổi thành các phép toán ẩn chữ.

Bạn không cần biết phép toán ẩn chữ là gì để giải bài toán này, vì chúng tôi sẽ cung cấp tất cả các định nghĩa cần thiết. Chúng tôi định nghĩa một phương trình ẩn chữ là một phương trình cộng được viết sao cho tất cả các số hạng (các số được cộng) và tổng được căn lề phải trên cùng một biên như thế này:

124
 31
 25
---
180

Ngoài ra, đối với mỗi cột của phương trình ẩn chữ, tất cả các chữ số của các số hạng trong cột đó phải khác nhau. Lưu ý rằng chúng tôi không bao gồm tổng trong ràng buộc này. Ví dụ, trong phương trình trên, cột thứ nhất chỉ chứa chữ số 1, cột thứ hai chứa các chữ số 2, 3 và 2, và cột thứ ba chứa các chữ số 4, 1 và 5. Phương trình này không phải là một phương trình ẩn chữ vì cột thứ hai chứa hai chữ số 2. Tuy nhiên, nó sẽ là một phương trình ẩn chữ nếu chúng ta thay số hạng cuối cùng bằng 15 (và tổng bằng 170).

Lưu ý rằng các số hạng trong một phương trình ẩn chữ luôn là số dương và được viết không có chữ số 0 ở đầu. Thứ tự của các số hạng không quan trọng (nói cách khác, hai phương trình chỉ khác nhau về thứ tự của các số hạng được coi là giống nhau).

Ví dụ trên là ở hệ cơ số 10, nhưng chúng tôi cũng quan tâm đến các phương trình ẩn chữ ở các hệ cơ số khác. Lưu ý rằng một "chữ số" trong hệ cơ số \(b\) có thể là bất kỳ số nguyên nào từ \(0\) đến \(b-1\). Dưới đây là một phương trình ẩn chữ trong hệ cơ số 23:

 I7B
 JJJ
----
1F47

Trong ví dụ này, "I" đại diện cho chữ số 18, "B" đại diện cho chữ số 11, "J" đại diện cho chữ số 19, và "F" đại diện cho chữ số 15. Trong hệ thập phân, hai số hạng là \(18 \cdot 23^2 + 7 \cdot 23 + 11 = 9694\) và \(19 \cdot 23^2 + 19 \cdot 23 + 19 = 10507\), và tổng là \(1 \cdot 23^3 + 15 \cdot 23^2 + 4 \cdot 23 + 7 = 20201\). Xin lưu ý rằng việc ký hiệu các chữ số từ 10 trở lên bằng các chữ cái chỉ nhằm mục đích làm rõ ví dụ; việc chúng ta ký hiệu các chữ số đó như thế nào trong thực tế không quan trọng trong bài toán này.

Có bao nhiêu phương trình ẩn chữ có tổng N cho trước trong hệ cơ số B cho trước?

Vì câu trả lời có thể rất lớn, hãy đưa ra kết quả theo modulo 1000000007.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, T. T dòng tiếp theo, mỗi dòng chứa hai số nguyên dương N và B. Tất cả các số đầu vào được cho ở hệ cơ số 10.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số lượng phương trình ẩn chữ khác nhau có tổng đã cho. Vì số này có thể rất lớn, hãy xuất kết quả theo modulo 1000000007. Tất nhiên, bản thân kết quả đầu ra phải ở hệ cơ số 10.

Ràng buộc

• \(1 \le \mathbf{T} \le 20\).

Phân nhóm

• Test set 1 (Visible):

• \(1 \le \mathbf{N} \le 100\).

• \(2 \le \mathbf{B} \le 10\).

• Test set 2 (Hidden):

• \(1 \le \mathbf{N} \le 10^{18}\).

• \(2 \le \mathbf{B} \le 70\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
6 10
8 4

Case #1: 4
Case #2: 4

6   1   2   1

-   5   4   2
6   -   -   3
    6   6   -
            6

20   11   13   10
--    3    1    3
20   --   --    1
     20   20   --
               20

Nguồn

Google Code Jam 2010, Vòng 3, bài Different Sum.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.