Phân chia chia hết

Đề bài

Ta có chuỗi \(\mathbf{S}\) gồm các chữ số thập phân. Một cách phân chia \(\mathbf{S}\) được tạo bằng cách chia \(\mathbf{S}\) thành các chuỗi con liên tiếp. Ví dụ, nếu \(\mathbf{S}\) là 0145217, hai cách phân chia có thể là 014 5 21 7 và 0 14 52 17. Mỗi chữ số phải thuộc đúng một chuỗi con và mỗi chuỗi con phải khác rỗng. Nếu \(\mathbf{S}\) có \(L\) chữ số thì có đúng \(2^{L-1}\) cách phân chia.

Với số nguyên dương \(\mathbf{D}\), một cách phân chia \(\mathbf{S}\) được gọi là chia hết cho \(\mathbf{D}\) nếu trong mọi cặp chuỗi con liên tiếp, có ít nhất một chuỗi biểu diễn một số nguyên hệ cơ số \(10\) chia hết cho \(\mathbf{D}\). Nếu \(\mathbf{D}=7\), cách phân chia thứ nhất ở trên là chia hết vì 014, 21 và 7 biểu diễn các số chia hết cho \(7\). Cách thứ hai không chia hết vì 52 và 17 liên tiếp nhưng không số nào chia hết cho \(7\). Cách phân chia 0145217 của chuỗi 0145217 chia hết cho mọi \(\mathbf{D}\) vì không có cặp chuỗi con liên tiếp.

Cho \(\mathbf{S}\) và \(\mathbf{D}\), hãy đếm số cách phân chia \(\mathbf{S}\) chia hết cho \(\mathbf{D}\). Vì kết quả có thể rất lớn, chỉ in phần dư khi chia cho số nguyên tố \(10^9+7\) (\(1000000007\)).

Dữ liệu vào

Dòng đầu chứa số bộ test \(\mathbf{T}\). \(\mathbf{T}\) dòng tiếp theo, mỗi dòng chứa một chuỗi chữ số \(\mathbf{S}\) và một số nguyên dương \(\mathbf{D}\) như trên.

Dữ liệu ra

Với mỗi bộ test, in một dòng dạng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ \(1\)), còn \(y\) là số cách phân chia khác nhau của \(\mathbf{S}\) chia hết cho \(\mathbf{D}\), lấy modulo \(10^9+7\) (\(1000000007\)).

Ràng buộc

\(1 \le \mathbf{T} \le 100\).

\(1 \le \mathbf{D} \le 10^6\).

Phân nhóm

Test Set 1 (Kết quả hiển thị)

\(1 \le\) độ dài của \(\mathbf{S} \le 1000\).

Test Set 2 (Kết quả ẩn)

\(1 \le\) độ dài của \(\mathbf{S} \le 10^5\).

Đ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 giữ nguyên điểm chính thức và tỷ lệ trên tổng điểm của bài.

Ví dụ

3
0145217 7
100100 10
5555 12

Case #1: 16
Case #2: 30
Case #3: 1

??? "Giải thích"
    Trong mẫu số 1, toàn bộ $16$ cách phân chia chia hết của $\mathbf{S}$ là: `0145217`, `0 145217`, `0 14 5217`, `0 14 5 217`, `0 14 5 21 7`, `0 14 521 7`, `0 145 217`, `0 145 21 7`, `0 14521 7`, `014 5217`, `014 5 217`, `014 5 21 7`, `014 521 7`, `0145 217`, `0145 21 7` và `014521 7`.

    Trong mẫu số 2, tổng cộng có $2^5=32$ cách phân chia. Để có hai chuỗi con liên tiếp đều không chia hết cho $10$, cả hai phải không kết thúc bằng $0$. Chỉ có $2$ cách như vậy là `1 001 00` và `1 001 0 0`, nên $30$ cách còn lại chia hết cho $10$.

    Trong mẫu số 3, không chuỗi con nào biểu diễn số chẵn, nên cũng không chuỗi con nào chia hết cho $12$. Vì vậy, cách duy nhất để không có hai chuỗi con liên tiếp đều không chia hết cho $12$ là hoàn toàn không có hai chuỗi con liên tiếp; chỉ có $1$ cách: `5555`.

Nguồn

Google Code Jam 2021, Chung kết thế giới, bài Divisible Divisions.

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