406121: GYM102270 C Divide

Đằng sau sự thành công của Bitcoin, không thể không kể đến công nghệ Blockchain. Blockchain hoạt động dựa trên các khối liên kết với nhau tạo thành một chuỗi. Điều đặc biệt ở đây chính là blockchain có độ bảo mật rất cao, không thể thay đổi.

Hacker b21 đã gây chấn động toàn cầu khi đã tìm ra cách hack được Blockchain. Anh đã mã hóa toàn bộ các block trở thành một số N. Số N này phải thỏa mãn điều kiện sau:

- Là một số tự nhiên.

- Chia hết cho x.

- thuộc khoảng [A, B].

- UCLN của chữ số thứ i tính từ phải qua trái và i phải bằng 1. (Ví dụ: 321 không thỏa mãn vì UCLN(1, 1) = 1, UCLN(2, 2) = 2, UCLN(3, 3) = 3 nhưng 231 thỏa mãn vì UCLN(1, 1) = 1, UCLN(3, 2) = 1, UCLN(2, 3) = 1) .

- Bao gồm các chữ số cho trước

Các bạn hãy giúp b21 tìm ra số lượng các số như thế nhé.

Dòng đầu tiên chứa ba số nguyên A, B, X.

Dòng thứ hai có xâu S chứa các chữ số 0..9 theo thứ tự tăng dần là các số có trong N

Chứa duy nhất 1 số nguyên là phần dư của phép chia kết quả bài toán cho 10⁹ + 7

B ≤ A

10% số test ứng với A, B, X ≤ 10³

30% số test ứng với A, B ≤ 10⁶, X ≤ 10⁵

30% số test ứng với A, B, X ≤ 10¹¹

30% số test ứng với A, B ≤ 10¹⁰⁰, X ≤ 10⁵

1 20 2
1234789

6

1 20 3
0123678

4

Giải thích test 1: 2, 4, 8, 12, 14, 18

Giải thích test 2: 3, 6, 12, 18