Роман — юный, но уже довольно известный в Ужляндии, математик. К сожалению, Сережа так не считает. Чтобы переубедить Сережу, Роман готов решить любую математическую задачу. Сережа, не долго думая, попросил Рому найти количество близких чисел к числу n по модулю m.
Число x называется близким к числу n по модулю m, если:
- его можно получить перестановкой цифр числа n,
- оно не имеет лидирующих нулей,
- остаток от деления числа x на m равен 0.
Роман — хороший математик, но поскольку различных вариантов ответа может быть очень много, ему будет трудно найти ответ. Поэтому он просит помощи у вас.
Выходные данные
В единственной строке выведите целое число — количество близких чисел к числу n по модулю m.
Примечание
В первом примере нам подходят числа: 104, 140, 410.
Во втором примере подходит единственное число 232.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
104 2
|
3
|
|
2
|
223 4
|
1
|
|
3
|
7067678 8
|
47
|