You are given an array a of length n and array b of length m both consisting of only integers 0 and 1. Consider a matrix c of size n × m formed by following rule: c_{i, j} = a_i ⋅ b_j (i.e. a_i multiplied by b_j). It's easy to see that c consists of only zeroes and ones too.

How many subrectangles of size (area) k consisting only of ones are there in c?

A subrectangle is an intersection of a consecutive (subsequent) segment of rows and a consecutive (subsequent) segment of columns. I.e. consider four integers x_1, x_2, y_1, y_2 (1 ≤ x_1 ≤ x_2 ≤ n, 1 ≤ y_1 ≤ y_2 ≤ m) a subrectangle c[x_1 ... x_2][y_1 ... y_2] is an intersection of the rows x_1, x_1+1, x_1+2, ..., x_2 and the columns y_1, y_1+1, y_1+2, ..., y_2.

The size (area) of a subrectangle is the total number of cells in it.

Input

The first line contains three integers n, m and k (1 ≤ n, m ≤ 40 000, 1 ≤ k ≤ n ⋅ m), length of array a, length of array b and required size of subrectangles.

The second line contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ 1), elements of a.

The third line contains m integers b_1, b_2, …, b_m (0 ≤ b_i ≤ 1), elements of b.

Output

Output single integer — the number of subrectangles of c with size (area) k consisting only of ones.

Examples

Input


3 3 2
1 0 1
1 1 1


Output


4


Input


3 5 4
1 1 1
1 1 1 1 1


Output


14

Note

In first example matrix c is:

<image>

There are 4 subrectangles of size 2 consisting of only ones in it:

<image>

In second example matrix c is:

<image>
import java.util.*;
import java.io.*;  

public class Solution{
    public static class pair{
        int x;
        int y;
    }
    public static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
        public String next() {
			while (st == null || !st.hasMoreElements())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) {
				a[i]=nextInt();
			}
			return a;
		}public double nextDouble() {
			return Double.parseDouble(next());
		}
    }
    public static void printarr(int[] arr){
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }
    static HashMap<Long,Integer> map;
    public static void main(String[] args) throws IOException{
        FastScanner fs=new FastScanner();
		int t=1; //fs.nextInt();
		PrintWriter out=new PrintWriter(System.out);
		while(t-->0){
		    int n=fs.nextInt();
		    int m=fs.nextInt();
		    int k=fs.nextInt();
		    int[] arr1=fs.readArray(n);
		    int[] arr2=fs.readArray(m);
		    ArrayList<Integer> row=new ArrayList<>();
		    ArrayList<Integer> col=new ArrayList<>();
		    for(int i=0;i<arr1.length;i++){
		        if(row.size()==0){
		            row.add(arr1[i]);
		        }else{
		            if(arr1[i]==0){
		                row.add(arr1[i]);
		            }else{
		                if(row.get(row.size()-1)>=1){
		                    int v=row.get(row.size()-1);
		                    row.set(row.size()-1,v+1);
		                }else{
		                    row.add(arr1[i]);
		                }
		            }
		        }
		    }
		    for(int i=0;i<arr2.length;i++){
		        if(col.size()==0){
		            col.add(arr2[i]);
		        }else{
		            if(arr2[i]==0){
		                col.add(arr2[i]);
		            }else{
		                if(col.get(col.size()-1)>=1){
		                    int v=col.get(col.size()-1);
		                    col.set(col.size()-1,v+1);
		                }else{
		                    col.add(arr2[i]);
		                }
		            }
		        }
		    }
		    Collections.sort(row,Collections.reverseOrder());
		    Collections.sort(col,Collections.reverseOrder());
		    ArrayList<Integer> si=fost(k);
		  //  System.out.println(si);
		    HashSet<Integer> set=new HashSet<>();
		    long ans=0;
		  //  System.out.println(row);
		  //  System.out.println(col);
		    for(int i=0;i<si.size();i++){
		        if(set.contains(si.get(i))){
		            continue;
		        }
		        set.add(si.get(i));
		        int r=si.get(i);
		        int c=k/si.get(i);
		        int j=0;
		        while(j<row.size()){
		            if(row.get(j)<r){
		                break;
		            }
		            int ch=0;
		            int z=j;
		            for(int g=j;g<row.size();g++){
		                if(row.get(g)==row.get(j)){
		                    ch++;
		                }else{
		                    break;
		                }
		                z=g+1;
		            }
		            for(int h=0;h<col.size();h++){
		                if(col.get(h)<c){
		                    break;
		                }
		                ans+=(long)((long)ch*((long)(row.get(j)-r+1)*(long)(col.get(h)-c+1)));
		            }
		            j=z;
		        }
		    }
		    System.out.println(ans);
		}
        out.close();
    }
    static ArrayList<Integer> fost(int k){
        ArrayList<Integer> li=new ArrayList<>();
        for(int i=1;i<=(int)Math.pow(k,0.5);i++){
            if(k%i==0){
                li.add(i);
                li.add(k/i);
            }
        }
        return li;
    }
    static long maxSubArraySum(int a[]) 
    { 
        int size = a.length; 
        long max_so_far = Long.MIN_VALUE, max_ending_here = 0; 
        int max=Integer.MIN_VALUE;
        for (int i = 0; i < size; i++) 
        { 
            max_ending_here = max_ending_here + a[i]; 
            if (max_so_far < max_ending_here) 
                max_so_far = max_ending_here; 
            if (max_ending_here < 0) 
                max_ending_here = 0; 
            max=Math.max(max,a[i]);
        } 
        if(max<0){
            return (long)0;
        }
        return max_so_far; 
    } 
    public static class Comp implements Comparator<pair>{
        public int compare(pair a,pair b){
            if(a.x!=b.x){
                return b.x-a.x;
            }else{
                return a.y-b.y;
            }
        }
    }
    public static long gcd(long a,long b){
        if (b == 0) 
        return a; 
        return gcd(b, a % b);
    }
    public static int lcm(int a,int b){
        int x=Math.max(a,b);
        int y=Math.min(a,b);
        long ans=x;
        while(ans%y!=0){
            ans+=x;
        }
        if(ans>Integer.MAX_VALUE){
            return -1;
        }
        return (int)ans;
    }
    public static long fact(int n){
        long ans=1;
        for(int i=1;i<=n;i++){
            ans*=i;
        }
        return ans;
    }
}