#1037. PERMN - Bao nhiêu số

Bộ nhớ: 256 MiB Thời gian: 2000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

NGUỒN: VOI Training Camp 3H (Ngày 01/11/2016 Am)

Dũng là một học sinh giỏi toán, rất nổi tiếng ở trong trường. Thật không may là Mai lại không nghĩ như vậy. Để làm cho Mai thay đổi quan niệm đó về mình, Dũng nói rằng anh ta có thể giải quyết bất kỳ bài toán nào. Sau khi suy nghĩ, Mai nói với Dũng là hãy đếm xem có bao nhiêu số là đóng với n theo modulo m ? Một số x được gọi là đóng với n theo modulo m nếu như:

  • x nhận được từ n bằng cách sắp xếp lại các chữ số của n
  • x không có chữ số 0 ở đầu
  • Phần dư của x khi chia cho m bằng 0

Dũng tuy rất giỏi toán, nhưng số lượng số là quá nhiều đối với anh ta. Viết chương trình giúp anh ta giải quyết vấn đề này.

Dữ liệu vào:

  • Một dòng chứa hai số nguyên n \left (1≤n≤10^{18}\right) và số m \left(1≤m≤100\right)

Dữ liệu ra:

  • Một số nguyên là kết quả tìm được

Ví dụ:

Dữ liệu vào:
104 2
Dữ liệu ra:
3
Dữ liệu vào:
223 4
Dữ liệu ra:
1
Dữ liệu vào:
7067678 8
Dữ liệu ra:
47