Một đoàn khảo cổ đang thám hiểm một hang động, và tình cờ tìm thấy một căn hầm từ thời cổ đại. Điều đặc biệt là căn hầm này mặc dù đã có từ xa xưa, nhưng lại có hệ thống mật mã giống như các hệ thống hiện đại. Trên cửa hầm có ghi một bài toán cổ, đáp án của bài toán đó chính là mật mã để vào trong căn hầm. Bài toán như sau: Cho trước hai số nguyên dương \(n\) và \(m\). Mật mã của căn hầm là số lượng số \(x\) gần với \(n\) mod \(m\). Biết rằng, một số nguyên dương \(x\) được gọi là gần với \(n\) mod \(m\) nếu như nó thỏa mãn các điều sau:

• \(x\) được tạo thành bằng cách hoán vị các chữ số của \(n\).
• \(x\) không bắt đầu bằng chữ số \(0\).
• \(x\) chia hết cho \(m\).

Yêu cầu

• Hãy giúp đoàn khảo cổ tìm ra mật mã của căn hầm?

Input

• Một dòng duy nhất chứa hai số nguyên dương \(n\) và \(m\) phân tách nhau bởi dấu cách.

Ràng buộc

• \(1 \le n \le 10^{18}\)
• \(1 \le m \le 100\)

Output

• Subtask 1 (40% số điểm): \(1 \le n \le 10^9\)
• Subtask 2 (60% số điểm): không có ràng buộc gì thêm

Input 1

104 2

Output 1

3

Input 2

223 4

Output 2

1

Input 3

7067678 8

Output 3

47