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>

    //package cf;
    import java.io.*;
    import java.util.*;
    import java.util.jar.JarOutputStream;

    public class Temp_Class {
        static int p=1000000007;
        static int max=(int)1e5;
        static List<Integer> l1=new ArrayList<>();
        static boolean prime[]=new boolean[max];

        public static void main(String[] args) throws Exception{
            BufferedWriter out = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(java.io.FileDescriptor.out), "ASCII"), 512);
            FastReader sc=new FastReader();
            int t=1;
            StringBuilder sb2=new StringBuilder();
            //
            // 12654
            while(t-- >0)
            {
                int n=sc.nextInt();
                int m=sc.nextInt();
                int k=sc.nextInt();
                HashMap<Integer,Integer> hash_a=new HashMap<>();
                HashMap<Integer,Integer> hash_b=new HashMap<>();
                int ar[]=new int[n];
                int br[]=new int[m];
                for(int i=0;i<n;i++)
                {
                    ar[i]=sc.nextInt();
                }
                TreeSet<Integer> a_bar=new TreeSet<>();
                TreeSet<Integer> b_bar=new TreeSet<>();
                for(int i=0;i<n;i++) {

                    int c=0;
                    while(i<n&&ar[i]==1)
                    {
                        i++;
                        c++;
                    }
                    if(c==0)
                        continue;
                    hash_a.put(c,hash_a.getOrDefault(c,0)+1);
                    a_bar.add(c);
                }
                    for(int i=0;i<m;i++)
                {
                    br[i]=sc.nextInt();

                }

                for(int i=0;i<m;i++)
                {
                    int c=0;
                    while(i<m&&br[i]==1)
                    {
                        i++;
                        c++;
                        }
                    if(c==0)
                        continue;
                    hash_b.put(c,hash_b.getOrDefault(c,0)+1);
                    b_bar.add(c);
                //    hash_b.put(c,hash_b.getOrDefault(c,0)+1);
                }
                List<Integer> pr=new ArrayList<>();
                for(int i=1;i<=Math.sqrt(k);i++)
                {
                    if(k%i==0)
                    {
                        pr.add(i);
                        pr.add(k/i);
                    }
                }
             /*   System.out.println(hash_a);
                System.out.println(hash_b);
                System.out.println(pr);
                System.out.println(a_bar.ceiling(4));
             */   long ans=0;
                for(int i=0;i<pr.size();i+=2) {
                    int l = pr.get(i);
                    int b = pr.get(i+1);
                        Integer ind_a = a_bar.ceiling(l);
                        Integer ind_b = b_bar.ceiling(b);
                        if(ind_a!=null&&ind_b!=null) {
                            List<Integer> t_a = new ArrayList<>(a_bar);
                            List<Integer> t_b = new ArrayList<>(b_bar);
                            //System.out.println(ind_a);
                            //System.out.println(t_a);
                           // System.out.println(ind_b);
                           // System.out.println(t_b);
                            for (int j = Collections.binarySearch(t_a, ind_a); j < t_a.size(); j++) {
                                for (int kk = Collections.binarySearch(t_b, ind_b); kk < t_b.size(); kk++) {
                                    ans += ((t_a.get(j) - l + 1)*hash_a.get(t_a.get(j))) * (t_b.get(kk) - b + 1)*hash_b.get(t_b.get(kk));
                                }
                            }
                        }

                    l=pr.get(i+1);
                    b=pr.get(i);
                     ind_a = a_bar.ceiling(l);
                     ind_b = b_bar.ceiling(b);
                    if (l!=b&&ind_a!=null&&ind_b!=null) {
                        List<Integer> t_a = new ArrayList<>(a_bar);
                        List<Integer> t_b = new ArrayList<>(b_bar);
                        for (int j = Collections.binarySearch(t_a, ind_a); j < t_a.size(); j++) {
                            for (int kk = Collections.binarySearch(t_b, ind_b); kk < t_b.size(); kk++) {
                                ans += (t_a.get(j) - l + 1) * (t_b.get(kk) - b + 1)*hash_a.get(t_a.get(j))*hash_b.get(t_b.get(kk));
                            }
                        }
                    }
                }
                System.out.println(ans);
            }
        //    System.out.println(sb2.toString());
            out.flush();
        }

        static  int ht[]=new int[max];

        public static long pow(long a,long b,long m)
        {
            long r=1;
            while(b!=1)
            {
                if(b%2!=0)
                    r=(r*a)%m;
                b=b>>1;
                a=(a*a)%m;
            }
            return (r*a)%m;
        }
        public static long gcd(long a,long b)
        {
            if(b>a)
            {
                a=a^b;
                b=a^b;
                a=a^b;
            }
            if(b==0)
                return a;
            return gcd(b,a%b);
        }
        public static void extgcd(long a,long b)
        {/*
            if(a==0)
            {
                x=0;
                y=1;
                d=b;
                // return ;
            }
            else
            {

                extgcd(b%a,a);

                long t=y;
                y=x;
                x=t-(b/a)*x;
            }*/
        }
        public static void dfs(List<Integer> adj[],int u,int p)
        {
            ht[u]=ht[p]==1?2:1;
            for(int v:adj[u])
            {
                if(v!=p)
                {
                    dfs(adj,v,u);
                }
            }
        }
        public static void seive()
        {
            for(int i=0;i<max;i++)
                prime[i] = true;

            for(int p = 2; p*p <=max; p++)
            {
                // If prime[p] is not changed, then it is a prime
                if(prime[p] == true)
                {
                    // Update all multiples of p
                    for(int i = p*p; i <=max; i += p)
                        prime[i] = false;
                }
            }

            // Print all prime numbers
            for(int i = 2; i <= max; i++)
            {
                if(prime[i] == true)
                {
                    l1.add(i);
                }
            }
        }
        public static boolean union(int a, int b, int p[], int r[]){
            // add your code here
            int pa=find(a,p,r);
            int pb=find(b,p,r);
            if(pa==pb)
                return true;
            if(pa!=pb)
            {
                if(r[pa]<r[pb])
                {
                    p[pa]=pb;
                }
                else if(r[pa]>r[pb])
                {
                    p[pb]=pa;
                }
                else
                {
                    p[pa]=pb;
                    r[pb]++;
                }
            }
            return false;
        }
        public static int find(int x,int p[],int r[])
        {
            if(p[x]==x)
                return x;
            p[x]=find(p[x],p,r);
            return p[x];
        }
        public static int binary_Search_upper(Long ar[],Long x)
        {
            int res=-1;
            int l=0;int r=ar.length-1;
            while(l<=r)
            {
                int mid=(l+r)>>1;
                if(ar[mid]==x)
                {
                    res=mid;
                    l=mid+1;
                }
                else if(ar[mid]>x)
                {
                    res=mid;
                    r=mid-1;
                }
                else
                {
                    l=mid+1;
                }
            }
            return res;
        }
        public static int binary_Search_lower(int ar[],int x)
        {
            int res=-1;
            int l=0;int r=ar.length-1;
            while(l<=r)
            {
                int mid=(l+r)>>1;
                if(ar[mid]==x)
                {
                    res=mid;
                    r=mid-1;
                }
                else if(ar[mid]>x)
                {
                    r=mid-1;
                }
                else
                {
                    res=mid;
                    l=mid+1;
                }
            }
            return res;
        }
        int bit[]=new int[(int)1e6];
        public void update(int n,int val,int i)
        {
            i++;
            while(i<n)
            {
                bit[i]+=val;
                i+=(i)&(-i);
            }

        }
        public long query(int n,int i)
        {
            i++;
            long sum=0;
            while(i>0)
            {
                sum+=bit[i];
                i-=(i)&(-i);
            }
            return sum;
        }


        ///////////////////////////////////////////////////////////////////////////////////
    //////////////////////////////////////////////////////////////////////////////////////////////
        static class FastReader {

            BufferedReader br;
            StringTokenizer st;

            public FastReader() {
                br = new BufferedReader(new InputStreamReader(System.in));
            }

            String next() {
                while (st == null || !st.hasMoreElements()) {
                    try {
                        st = new StringTokenizer(br.readLine());
                    } catch (IOException e) {
                        e.printStackTrace();
                    }
                }
                return st.nextToken();
            }

            int nextInt() {
                return Integer.parseInt(next());
            }

            long nextLong() {
                return Long.parseLong(next());
            }

            double nextDouble() {
                return Double.parseDouble(next());
            }

            String nextLine() {
                String str = "";
                try {
                    str = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                return str;
            }
        }


    }
