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 java.math.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(System.out);
        //Scanner sc = new Scanner();
        Reader in = new Reader();
        Main solver = new Main();
        solver.solve(out, in);
        out.flush();
        out.close();
 
    }
 
    static int INF = (int)1e9;
    static int maxn = 2*(int)1e5+5;
    static int mod = (int)1e9+7 ;
    static int n,m,t,q,d,p,k;
    static ArrayList<Integer> arr;
    
    void solve(PrintWriter out, Reader in) throws IOException{
        n = in.nextInt();
        m = in.nextInt();
        k = in.nextInt();
        
        
        int[] a = new int[n];
        int[] b = new int[m];
        for (int i = 0; i < n; i++) a[i] = in.nextInt();
        for (int i = 0; i < m; i++) b[i] = in.nextInt();
        
        arr = new ArrayList<Integer>();
        int cnt = 0;
        for (int i = 0; i < m; i++) {
            if (b[i] == 0 && cnt != 0) {
                arr.add(cnt);
                cnt = 0;
            } else if (b[i] == 1) cnt++;
        }
        if (cnt != 0) arr.add(cnt);
        Collections.sort(arr,Collections.reverseOrder());
        
        int[] pre = new int[arr.size()];
        for (int i = 0; i < arr.size(); i++) {
            pre[i] = arr.get(i);
            if (i != 0) pre[i] += pre[i-1];
        }
        
        long[] ans = new long[n+1];
        long[] aux = new long[n+1];
        int div = 0, bss = 0, tmp = 0;
        for (int i = 1; i <= n; i++) {
            if (k%i != 0) continue;
            div = k/i;
            
            bss = bs(div);
            if (bss != -1) {
                tmp = pre[bss]-(bss+1)*div+bss+1;
                ans[i] = tmp;
                aux[i] = tmp;
            }
        }
        
        for (int i = 2; i <= n; i++) {
            aux[i] += aux[i-1];
            ans[i] = ans[i-1]+aux[i];
        }
        
        
        
        arr.clear();
        cnt = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] == 0 && cnt != 0) {
                arr.add(cnt);
                cnt = 0;
            } else if (a[i] == 1) cnt++;
        }
        if (cnt != 0) arr.add(cnt);
        
        long res = 0;
        for (int i = 0; i < arr.size(); i++){
            res += ans[arr.get(i)];
        }
        out.println(res);
    }
    
    //<>
    
    static int bs(int x) {
        int lo = 0, hi = arr.size()-1, mid, res = -1;
        
        while (lo <= hi) {
            mid = (lo+hi)/2;
            
            if (arr.get(mid) >= x) {
                res = mid;
                lo = mid +1;
            } else {
                hi = mid -1;
            }
        }
        return res;
    }
    
    static class Reader {
 
    private InputStream mIs;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
 
    public Reader() {
        this(System.in);
    }
 
    public Reader(InputStream is) {
        mIs = is;
    }
 
    public int read() {
        if (numChars == -1) {
            throw new InputMismatchException();
 
    }
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = mIs.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0) {
                return -1;
            }
        }
        return buf[curChar++];
    }
 
    public String nextLine() {
        int c = read();
        while (isSpaceChar(c)) {
            c = read();
        }
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isEndOfLine(c));
        return res.toString();
    }
 
    public String next() {
        int c = read();
        while (isSpaceChar(c)) {
            c = read();
        }
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }
 
    double nextDouble()
    {
        return Double.parseDouble(next());
    }
 
    public long nextLong() {
        int c = read();
        while (isSpaceChar(c)) {
            c = read();
        }
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        long res = 0;
        do {
            if (c < '0' || c > '9') {
                throw new InputMismatchException();
            }
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }
 
    public int nextInt() {
        int c = read();
        while (isSpaceChar(c)) {
            c = read();
        }
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9') {
                throw new InputMismatchException();
            }
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }
 
    public boolean isSpaceChar(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }
 
    public boolean isEndOfLine(int c) {
        return c == '\n' || c == '\r' || c == -1;
    }
 
    }
}