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.util.*;

public class Main {
	public static void main(String[] args) throws Exception {
		
		Scanner in = new Scanner(System.in);
		String n = in.next();
		int m = in.nextInt();
		
		byte[] nums = new byte[10];
		for(char ch: n.toCharArray()) {
			++nums[Character.digit(ch, 10)];
		}
		int total = 1;
		for(byte num: nums) {
			total *= num + 1;
		}
		
		long[][] dp = new long[total][m];
		dp[0][0] = 1;
		
		for(int i = 1; i < total; ++i) {
			for(int j = 0; j < m; ++j) {
				int d = 1;
				int numCount = 0;
				for(int k = 0; k < 10; ++k) {
					if(nums[k] != 0) {
						numCount += i / d % (nums[k] + 1);
						d *= nums[k] + 1;
					}
				}
				d = 1;
				long level = Fun.power(10, numCount - 1);
				for(int k = 0; k < 10; ++k) {
					if(nums[k] != 0) {
						int count = i / d % (nums[k] + 1);
						if(count != 0) {
							int currem = (int) (k * level % m);
							dp[i][j] += dp[i / (d * (nums[k] + 1)) * (d * (nums[k] + 1)) + (count - 1) * d + i % d][(j + m - currem) % m];
						}
						d *= nums[k] + 1;
					}
				}
			}
		}
		
		if(nums[0] == 0) {
			System.out.println(dp[total - 1][0]);
		} else {
			System.out.println(dp[total - 1][0] - dp[total - 1 - 1][0]);
		}
	}

}

// ///////////////////////////////////////////////////////////
// ///////////////////////////////////////////////////////////

class Fun {
	
	public static long power(long n, long e) {
		long result = 1;
		for(long i = 0; i < e; ++i) {
			result *= n;
		}
		return result;
	}
	
	public static int[] nextInts(Scanner in, int count) {
		int[] result = new int[count];
		for (int i = 0; i < count; ++i) {
			result[i] = in.nextInt();
		}
		return result;
	}
	
	public static boolean isPrime(int n) {
		boolean result = true;
		for(int i = 2; i * i <= n; ++i) {
			if(n % i == 0) {
				result = false;
				break;
			}
		}
		return result;
	}

	public static long gcd(long a, long b) {
		if (b == 0)
			return a;
		return gcd(b, a % b);
	}

	public static int gcd(int a, int b) {
		if (b == 0)
			return a;
		return gcd(b, a % b);
	}

	public static long lcm(long a, long b) {
		return a / gcd(a, b) * b;
	}

	public static int[][] transpose(int[][] mat) {
		int r = mat.length;
		int c = mat[0].length;
		int[][] result = new int[c][r];
		for (int i = 0; i < c; ++i)
			for (int j = 0; j < r; ++j)
				result[i][j] = mat[j][i];
		return result;
	}

	public static String repeatString(String s, long count) {
		StringBuilder sb = new StringBuilder();
		for (long i = 0; i < count; ++i) {
			sb.append(s);
		}
		return sb.toString();
	}
}

class Treap<K extends Comparable<? super K>, V> {
	
	Treap() {
		nullNode = new TreapNode<K, V>();
		nullNode.left = nullNode.right = nullNode;
		nullNode.priority = Integer.MAX_VALUE;
		rootNode = nullNode;
	}
	
	public V put(K key, V value) {
		PutResult<K, V> putResult = putHelp(rootNode, key, value);
		rootNode = putResult.newNode;
		return putResult.originalValue;
	}
	
	public V get(K key) {
		TreapNode<K, V> currentNode = rootNode;
		while(currentNode != nullNode && currentNode.key.compareTo(key) != 0) {
			if(key.compareTo(currentNode.key) < 0) {
				currentNode = currentNode.left;
			} else {
				currentNode = currentNode.right;
			}
		}
		
		if(currentNode == nullNode) {
			return null;
		} else {
			return currentNode.value;
		}
	}
	
	public V remove(K key) {
		V result = get(key);
		if(result != null) {
			rootNode = removeHelp(rootNode, key);
		}
		return result;
	}
	
	public K select(int rank) {
		if(rank >= size() || rank < 0) {
			return null;
		}
		TreapNode<K, V> currentNode = rootNode;
		while(rank != currentNode.left.size) {
			if(rank < currentNode.left.size) {
				currentNode = currentNode.left;
			} else {
				rank -= currentNode.left.size + 1;
				currentNode = currentNode.right;
			}
		}
		
		return currentNode.key;
	}
	
	public int rank(K key) {
		if(rootNode == nullNode) {
			return -1;
		}
		int result = rootNode.left.size;
		TreapNode<K, V> currentNode = rootNode;
		while(currentNode != nullNode && currentNode.key.compareTo(key) != 0) {
			if(key.compareTo(currentNode.key) < 0) {
				result -= currentNode.left.right.size + 1;
				currentNode = currentNode.left;
			} else {
				result += currentNode.right.left.size + 1;
				currentNode = currentNode.right;
			}
		}
		
		if(currentNode == nullNode) {
			return -1;
		} else {
			return result;
		}
	}
	
	public void clear() {
		rootNode = nullNode;
	}
	
	public int size() {
		return rootNode.size;
	}
	
	private static class TreapNode<K, V> {
		public K key;
		public V value;
		public int size;
		public int priority;
		TreapNode<K, V> left, right;
	}
	
	private static class PutResult<K, V> {
		public TreapNode<K, V> newNode;
		public V originalValue;
	}
	
	private PutResult<K, V> putHelp(TreapNode<K, V> node, K key, V value) {
		if(node == nullNode) {
			PutResult<K, V> result = new PutResult<K, V>();
			result.newNode = new TreapNode<K, V>();
			result.newNode.key = key;
			result.newNode.value = value;
			result.newNode.size = 1;
			result.newNode.priority = randomPriority.nextInt(Integer.MAX_VALUE);
			result.newNode.left = result.newNode.right = nullNode;
			return result;
		} else if(key.compareTo(node.key) == 0) {
			PutResult<K, V> result = new PutResult<K, V>();
			result.originalValue = node.value;
			node.value = value;
			result.newNode = node;
			return result;
		} else if(key.compareTo(node.key) < 0) {
			PutResult<K, V> result = putHelp(node.left, key, value);
			node.left = result.newNode;
			if(result.originalValue == null) {
				++node.size;
				if(node.left.priority < node.priority) {
					node = rightRotate(node);
				}
			}
			result.newNode = node;
			return result;
		} else {
			PutResult<K, V> result = putHelp(node.right, key, value);
			node.right = result.newNode;
			if(result.originalValue == null) {
				++node.size;
				if(node.right.priority < node.priority) {
					node = leftRotate(node);
				}
			}
			result.newNode = node;
			return result;
		}
	}
	
	private TreapNode<K, V> removeHelp(TreapNode<K, V> node, K key) {
		if(key.compareTo(node.key) == 0) {
			node = removeHelp2(node);
		} else if(key.compareTo(node.key) < 0) {
			--node.size;
			node.left = removeHelp(node.left, key);
		} else {
			--node.size;
			node.right = removeHelp(node.right, key);
		}
		return node;
	}
	
	private TreapNode<K, V> removeHelp2(TreapNode<K, V> node) {
		if(node.left == nullNode && node.right == nullNode) {
			return nullNode;
		}
		
		if(node.left.priority < node.right.priority) {
			node = rightRotate(node);
			--node.size;
			node.right = removeHelp2(node.right);
		} else {
			node = leftRotate(node);
			--node.size;
			node.left = removeHelp2(node.left);
		}
		return node;
	}
	
	private TreapNode<K, V> leftRotate(TreapNode<K, V> node) {
		TreapNode<K, V> result = node.right;
		node.right = result.left;
		result.left = node;
		result.size = node.size;
		node.size -= 1 + result.right.size;
		return result;
	}
	
	private TreapNode<K, V> rightRotate(TreapNode<K, V> node) {
		TreapNode<K, V> result = node.left;
		node.left = result.right;
		result.right = node;
		result.size = node.size;
		node.size -= 1 + result.left.size;
		return result;
	}
	
	private TreapNode<K, V> nullNode;
	private TreapNode<K, V> rootNode;
	private Random randomPriority = new Random();
}