Roman and Numbers

题意翻译

将n(n<=10^18)的各位数字重新排列(不允许有前导零) 求 可以构造几个mod m等于0的数字 提供者:@zhoutb2333

题目描述

Roman is a young mathematician, very famous in Uzhland. Unfortunately, Sereja doesn't think so. To make Sereja change his mind, Roman is ready to solve any mathematical problem. After some thought, Sereja asked Roma to find, how many numbers are close to number $ n $ , modulo $ m $ . Number $ x $ is considered close to number $ n $ modulo $ m $ , if: - it can be obtained by rearranging the digits of number $ n $ , - it doesn't have any leading zeroes, - the remainder after dividing number $ x $ by $ m $ equals 0. Roman is a good mathematician, but the number of such numbers is too huge for him. So he asks you to help him.

输入输出格式

输入格式


The first line contains two integers: $ n $ $ (1<=n&lt;10^{18}) $ and $ m $ $ (1<=m<=100) $ .

输出格式


In a single line print a single integer — the number of numbers close to number $ n $ modulo $ m $ .

输入输出样例

输入样例 #1

104 2

输出样例 #1

3

输入样例 #2

223 4

输出样例 #2

1

输入样例 #3

7067678 8

输出样例 #3

47

说明

In the first sample the required numbers are: 104, 140, 410. In the second sample the required number is 232.