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