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.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Map;
import java.util.HashMap;
public class Main {

    private static List<Pair> findDivisorPairs(int k){
        List<Pair> divisorPairs = new ArrayList<>();
        int sqr = (int)Math.sqrt(k);
        for(int i = 1; i <= sqr; ++i) {
            if ((k % i) == 0) {
                if ((k / i) == i) {
                    divisorPairs.add(new Pair(i, i));
                } else {
                    divisorPairs.add(new Pair(i, k / i));
                    divisorPairs.add(new Pair(k / i, i));
                }
            }
        }
        return divisorPairs;
    }

    public static void main(String [] commandLineArgument){

        Scanner input = new Scanner(System.in);
        int n = input.nextInt() , m = input.nextInt() , k = input.nextInt();
        int [] a = new int[n];
        int [] b = new int[m];
        Map<Integer, Integer> aStore = new HashMap<>();
        Map<Integer , Integer> bStore = new HashMap<>();
        cal(input, n, a, aStore);
        cal(input, m, b, bStore);
        List<Pair> divisorPairs = findDivisorPairs(k);

        long answer = 0;
        for(Map.Entry<Integer , Integer> aEntry : aStore.entrySet()){
            int aValue = aEntry.getKey();
            int aCount = aEntry.getValue();
            for(Map.Entry<Integer , Integer> bEntry : bStore.entrySet()){
                int bValue = bEntry.getKey();
                int bCount = bEntry.getValue();
                for(Pair pairs : divisorPairs){
                    int row = pairs.first;
                    int col = pairs.second;

                    if(row <= aValue && col <= bValue){
                        int first = aValue - row + 1;
                        int second = bValue - col + 1;
                        long total = first *1l* second;
                        answer += (total *1l* (aCount *1l* bCount));
                    }
                }
            }
        }
        System.out.println(answer);
        input.close();
    }

    private static void cal(Scanner input, int n, int[] a, Map<Integer, Integer> Store) {
        int oneCount = 0;
        for(int i = 0; i < n; ++i){
            a[i] = input.nextInt();
            if(a[i] == 0){
                Store.put(oneCount , Store.getOrDefault(oneCount , 0) + 1);
                oneCount = 0;
                continue;
            }
            ++oneCount;
        }
        if(oneCount != 0){
            Store.put(oneCount , Store.getOrDefault(oneCount , 0) + 1);
        }
    }
}

class Pair {
    public int first;
    public int second;
    Pair(int first , int second){
        this.first = first;
        this.second = second;
    }

    @Override
    public String toString() {
        return "Pair{" +
                "first=" + first +
                ", second=" + second +
                '}';
    }
}
