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.*;
import static java.lang.Math.*;
import static java.lang.System.*;
public class B
{
    public static void main(String[]args){
        InputReader sc = new InputReader(System.in);
        PrintWriter pw =new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        int len=sc.nextInt();
        int wid=sc.nextInt();
        int size=sc.nextInt();
        int[]length=sc.nextIntArray(len);
        int[]width=sc.nextIntArray(wid);
        ArrayList<Integer>arr1=new ArrayList<Integer>();
        ArrayList<Integer>arr2=new ArrayList<Integer>();
        for(int i=0;i<len;i++){
        	if(length[i]==1){
        		int c=1;
        		for(int a=i+1;a<len&&length[a]==1;a++){
        			c++;
        		}
        		i=i+c;
        		arr1.add(c);
        	}
        }
        for(int i=0;i<wid;i++){
        	if(width[i]==1){
        		int c=1;
        		for(int a=i+1;a<wid&&width[a]==1;a++){
        			c++;
        		}
        		i=i+c;
        		arr2.add(c);
        	}
        }
        long total=0;
        ArrayList<Integer>factor1=new ArrayList<Integer>();
        ArrayList<Integer>factor2=new ArrayList<Integer>();
        
        for(int i=1;i<=(int)Math.sqrt(size);i++){
            if(size%i!=0)continue;
            int a=size/i;
            factor1.add(i);
            factor2.add(a);
            if(i!=a){
                factor1.add(a);
                factor2.add(i);
            }
        }
        for(int z=0;z<factor1.size();z++){
        	int i=factor1.get(z);
        	int a=factor2.get(z);
        	int per=0;
        	int per2=0;
        	for(int b=0;b<arr2.size();b++){
        		if(arr2.get(b)>=a)per+=arr2.get(b)-a+1;
        	}
        	for(int b=0;b<arr1.size();b++){
        		if(arr1.get(b)>=i)per2+=arr1.get(b)-i+1;	
        	}
        	total+=per*per2;
        }
        System.out.println(total);
        pw.flush();
    }
    
    static class InputReader
    {
        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;
        private SpaceCharFilter filter;
        public InputReader(InputStream stream)
        {
                this.stream = stream;
        }
        public int snext()
        {
                if (snumChars == -1)
                        throw new InputMismatchException();
                if (curChar >= snumChars)
                {
                        curChar = 0;
                        try
                        {
                                snumChars = stream.read(buf);
                        } catch (IOException e)
                        {
                                throw new InputMismatchException();
                        }
                        if (snumChars <= 0)
                                return -1;
                }
                return buf[curChar++];
        }
        public int nextInt()
        {
                int c = snext();
                while (isSpaceChar(c))
                {
                        c = snext();
                }
                int sgn = 1;
                if (c == '-')
                {
                        sgn = -1;
                        c = snext();
                }
                int res = 0;
                do
                {
                        if (c < '0' || c > '9')
                                throw new InputMismatchException();
                        res *= 10;
                        res += c - '0';
                        c = snext();
                } while (!isSpaceChar(c));
                return res * sgn;
        }
        public long nextLong()
        {
                int c = snext();
                while (isSpaceChar(c))
                {
                        c = snext();
                }
                int sgn = 1;
                if (c == '-')
                {
                        sgn = -1;
                        c = snext();
                }
                long res = 0;
                do
                {
                        if (c < '0' || c > '9')
                                throw new InputMismatchException();
                        res *= 10;
                        res += c - '0';
                        c = snext();
                } while (!isSpaceChar(c));
                return res * sgn;
        }
        public double nextDouble()
        {
                int c = snext();
                while (isSpaceChar(c))
                {
                        c = snext();
                }
                int sgn = 1;
                if (c == '-')
                {
                        sgn = -1;
                        c = snext();
                }
                double res = 0;
                while(c<='9'&&c>='0'){
                    res*=10;
                    res+=c-'0';
                    c=snext();
                }
                if(c=='.'){
                    double decimal=0;
                    long multiplier=1;
                    c=snext();
                    do
                    {
                        if (c < '0' || c > '9')
                                throw new InputMismatchException();
                        decimal *= 10;
                        decimal += c - '0';
                        multiplier*=10;
                        c = snext();
                    } while (!isSpaceChar(c));
                    return sgn*(res+decimal/multiplier);
                }else{
                    if(!isSpaceChar(c)){
                        throw new InputMismatchException();
                    }
                    return sgn*res;
                }
        }
        public int[] nextIntArray(int n)
        {
                int a[] = new int[n];
                for (int i = 0; i < n; i++)
                {
                        a[i] = nextInt();
                }
                return a;
        }
        public long[] nextLongArray(int n)
        {
                long a[] = new long[n];
                for (int i = 0; i < n; i++)
                {
                        a[i] = nextLong();
                }
                return a;
        }
        public String next(){return readString();}
        public String readString()
        {
                int c = snext();
                while (isSpaceChar(c))
                {
                        c = snext();
                }
                StringBuilder res = new StringBuilder();
                do
                {
                        res.appendCodePoint(c);
                        c = snext();
                } while (!isSpaceChar(c));
                return res.toString();
        }
        public String nextLine()
        {
                int c = snext();
                StringBuilder res = new StringBuilder();
                do
                {
                        res.appendCodePoint(c);
                        c = snext();
                } while (!isEndOfLine(c));
                if(isEndOfLine(res.charAt(res.length()-1)))
                return res.deleteCharAt(res.length()).toString();
                return res.toString();
        }
        public ArrayList<String> readAll(){
            ArrayList<String>a=new ArrayList<String>();
            try{
                while(true){
                    a.add(nextLine());
                }
            }catch(Exception e){
                
            }
            return a;
        }
        public boolean hasNext(){
            boolean hasnext=true;
            try{
                hasnext= stream.available()!=0;
            }catch(IOException e){
            }
            return hasnext||curChar<snumChars;
        }
        public boolean isSpaceChar(int c)
        {
                if (filter != null)
                        return filter.isSpaceChar(c);
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
        private boolean isEndOfLine(int c)
        {
                return c == '\n' || c == '\r' || c == -1;
        }
        public interface SpaceCharFilter
        {
                public boolean isSpaceChar(int ch);
        }
    }
}