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.

Input

The first line contains two integers: n (1 ≤ n < 1018) and m (1 ≤ m ≤ 100).

Output

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

Examples

Input

104 2


Output

3


Input

223 4


Output

1


Input

7067678 8


Output

47

Note

In the first sample the required numbers are: 104, 140, 410.

In the second sample the required number is 232.

import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.Map.Entry;


public class Main{
	public static class FastReader {
		BufferedReader br;
		StringTokenizer root;
		
 
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
 
		String next() {
			while (root == null || !root.hasMoreTokens()) {
				try {
					root = new StringTokenizer(br.readLine());
				} catch (Exception addd) {
					addd.printStackTrace();
				}
			}
			return root.nextToken();
		}
 
		int nextInt() {
			return Integer.parseInt(next());
		}
 
		double nextDouble() {
			return Double.parseDouble(next());
		}
 
		long nextLong() {
			return Long.parseLong(next());
		}
 
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception addd) {
				addd.printStackTrace();
			}
			return str;
		}
	}
	
	public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
	
	public static FastReader sc = new FastReader();
 
	static int mod = (int) (1e2),m,n;
	static List<Integer>[] edges ;
	static long[][] dp ;
	static int[] a;
	static long[] pre;
	static char[] s,t;
	public static void main(String[] args) {

	 int t = 1;
	 while(t-->0) {
		 s = sc.next().toCharArray();
		 n = s.length;
		 m = sc.nextInt();
		
		 dp = new long[1<<n][m];
		 for(int i=0;i<dp.length;++i) {
			 Arrays.fill(dp[i], -1);
		 }
		 out.print(f(0,0));
	 }
		
	out.close();
}
	private static long f(int mask, int mod) {
		if(Long.bitCount(mask) == n) {
			if(mod == 0) return 1; // if all numbers are covered 
			else return 0;
		}
		if(dp[mask][mod] != -1) return dp[mask][mod];
		long ans = 0;
		boolean[] set = new boolean[10];
		for(int i=0;i<s.length;++i) {
			int x = s[i]-'0';
			if(mask == 0 && x == 0) continue; // prevent leading zeroes
			if(set[x]) continue; // already used 
			if((mask&(1<<i))!=0) continue; // not used 
			set[x] = true;
			ans+=f(mask|(1<<i),(mod*10+x)%m);
		}
		return dp[mask][mod] = ans;
	}
	
}

