← 返回题目列表

Codeforces · 401/D

D. 罗马和数字

中文机器翻译题面 查看原题

Roman是一位年轻的数学家,在乌日兰非常有名。不幸的是,Sereja 并不这么认为。为了让塞雷贾改变主意,罗曼准备解决任何数学问题。经过一番思考,Sereja 让 Roma 找出有多少个数字接近于 n 模 m 的数字。

数字 x 被认为接近数字 n 模 m,如果:

- 可以通过重新排列数字n的数字来获得,
- 它没有任何前导零,
- 数字 x 除以 m 后的余数等于 0。

罗曼是一位优秀的数学家,但这样的数字对他来说太大了。所以他请求你帮助他。

输入

第一行包含两个整数:n (1 ≤ n < 1018) 和 m (1 ≤ m ≤ 100)。

输出

在一行中打印一个整数 — 接近数字 n 模 m 的数字数量。

示例

输入 #1

104 2

输出 #1

3

输入 #2

223 4

输出 #2

1

输入 #3

7067678 8

输出 #3

47

注意

在第一个示例中,所需的数字为:104、140、410。

在第二个示例中,所需的数量是 232。