You have a string of decimal digits s. Let's define bij = si·sj. Find in matrix b the number of such rectangles that the sum bij for all cells (i, j) that are the elements of the rectangle equals a in each rectangle.

A rectangle in a matrix is a group of four integers (x, y, z, t) (x ≤ y, z ≤ t). The elements of the rectangle are all cells (i, j) such that x ≤ i ≤ y, z ≤ j ≤ t.

Input

The first line contains integer a (0 ≤ a ≤ 109), the second line contains a string of decimal integers s (1 ≤ |s| ≤ 4000).

Output

Print a single integer — the answer to a problem.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

10
12345


Output

6


Input

16
439873893693495623498263984765


Output

40
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Matrix {
    public static void main(String[] args) throws IOException{
    	BufferedReader reader = null;
    	try {
    		reader = new BufferedReader(new InputStreamReader(System.in));
    		long a = Long.parseLong(reader.readLine());
    		String s = reader.readLine();
    		int n = s.length();
    		TreeMap<Long, Integer> map = new TreeMap<Long, Integer>(); 
			for(int i=0;i<n;i++){
				long sum = 0;
				for(int j=i;j<n;j++){
					int v = s.charAt(j) - 48;
					sum += v;
					boolean add = false;
					if(sum!=0){
						if(sum <= a && a%sum == 0)
							add=true;
					}else{
						if(a == 0)
							add=true;
					}
					if(add){
						if(!map.containsKey(sum)){
							map.put(sum, 1);
						}else{
							map.put(sum, map.get(sum) + 1);
						}
					}
				}
			}
			long count = 0;
			for(long key:map.keySet()){
				long size = map.get(key);
				if(a==0&&key==0){
					count+=size*n*(n+1) - size*size;
				}else if(key!=0){
					long rest = a/key;
					if(map.containsKey(rest)){
						count += size*map.get(rest);
					}
				}
			}
			System.out.println(count);
    	} finally {
    		if(reader != null)
			reader.close();
		}
	}
}
