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 javafx.util.Pair;
import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class Main implements Runnable
{
    boolean multiple = false;
    long MOD = 998244353;

    @SuppressWarnings("Duplicates")
    void solve() throws Exception
    {
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        /*read long arr a of size n*/ long[] a = new long[n]; for (int I = 0; I < n; I++) a[I] = sc.nextLong();
        /*read int arr b of size m*/ int[] b = new int[m]; for (int I = 0; I < m; I++) b[I] = sc.nextInt();
        long ans = 0;
        for (long divisor = 1; divisor * divisor <= k; divisor++)
        {
            if (k % divisor != 0) continue;
//            System.out.println();
//            System.out.println(divisor);
            long target = k / divisor;
            long c1 = 0, c2 = 0;

            long curr = 0;
            for (int i = 0; i < n; i++)
            {
                if (a[i] == 0) curr = 0;
                else curr++;
                if (curr >= divisor) c1++;
            }
            curr = 0;
            for (int i = 0; i < m; i++)
            {
                if (b[i] == 0) curr = 0;
                else curr++;
                if (curr >= target) c2++;
            }
//            System.out.println(c1);
//            System.out.println(c2);
            ans += c1 * c2;

            if (target == divisor) continue;

            c1 = 0; c2 = 0;
            curr = 0;
            for (int i = 0; i < n; i++)
            {
                if (a[i] == 0) curr = 0;
                else curr++;
                if (curr >= target) c1++;
            }
            curr = 0;
            for (int i = 0; i < m; i++)
            {
                if (b[i] == 0) curr = 0;
                else curr++;
                if (curr >= divisor) c2++;
            }
//            System.out.println(c1);
//            System.out.println(c2);
            ans += c1 * c2;
        }
        System.out.println(ans);
    }

    class Segtree
    {
        long[] t;
        int n;

        long f(long a, long b)
        {
            return min(a, b);
        }

        void modify(int p, long value) {  // set value at position p
            for (t[p+=n] = value; (p /= 2) != 0;) t[p] = f(t[2*p], t[2*p+1]);
        }

        long query(long l, long r) {
            long resl=0, resr=0;
            for (l += n, r += n; l < r; l /= 2, r /= 2) {
                if ((l&1) != 0) resl = f(resl, t[(int)(l++)]);
                if ((r&1) != 0) resr = f(t[(int)(--r)], resr);
            }
            return max(resl, resr);
        }

        Segtree(int N) { n = N; t = new long[2 * n]; };
    }

    TreeMap<Integer, TreeSet<Integer>> buildGraph(int n, int m) throws Exception{TreeMap<Integer, TreeSet<Integer>> graph = new TreeMap<>();for (int i = 1; i <= n; i++) graph.put(i, new TreeSet<>());for (int i = 0; i < m; i++) { int u = sc.nextInt();int v = sc.nextInt();graph.get(u).add(v);graph.get(v).add(u); }return graph; }
    TreeMap<Integer, TreeSet<Integer>> buildDirGraph(int n, int m) throws Exception { TreeMap<Integer, TreeSet<Integer>> graph = new TreeMap<>();for (int i = 1; i <= n; i++) graph.put(i, new TreeSet<>());for (int i = 0; i < m; i++) graph.get(sc.nextInt()).add(sc.nextInt());return graph; }
    TreeMap<Integer, TreeSet<Integer>> revGraph(TreeMap<Integer, TreeSet<Integer>> graph) { TreeMap<Integer, TreeSet<Integer>> rev = new TreeMap<>();for (Integer u : graph.keySet()) rev.put(u, new TreeSet<>());for (Integer u : graph.keySet()) for (Integer v : graph.get(u)) rev.get(v).add(u);return rev; }
    TreeMap<Long, Integer> counts(long[] arr) { TreeMap<Long, Integer> counts = new TreeMap<>(); for (long a : arr) { if (!counts.containsKey(a)) counts.put(a, 0); counts.put(a, counts.get(a) + 1);} return counts; }
    String reverse(String s, int i, int j) /*[i, j] closed*/ { return (i > j) ? reverse(s, j, i) : s.substring(0, i) + (new StringBuilder(s.substring(i, j + 1))).reverse() + ((j + 1 <= s.length() - 1) ? s.substring(j + 1) : "");}

    @Override public void run() { try { in = new BufferedReader(new InputStreamReader(System.in));out = new PrintWriter(System.out);sc = new FastScanner(in);if (multiple) { int q = sc.nextInt();for (int i = 0; i < q; i++) solve(); } else solve(); } catch (Throwable uncaught) { Main.uncaught = uncaught; } finally { out.close(); }} public static void main(String[] args) throws Throwable{ Thread thread = new Thread(null, new Main(), "", (1 << 26));thread.start();thread.join();if (Main.uncaught != null) {throw Main.uncaught;} } static Throwable uncaught; BufferedReader in; FastScanner sc; PrintWriter out; } class FastScanner { BufferedReader in; StringTokenizer st; public FastScanner(BufferedReader in) {this.in = in;}public String nextToken() throws Exception { while (st == null || !st.hasMoreTokens()) { st = new StringTokenizer(in.readLine()); }return st.nextToken(); }public int nextInt() throws Exception { return Integer.parseInt(nextToken()); }public long nextLong() throws Exception { return Long.parseLong(nextToken()); }public double nextDouble() throws Exception { return Double.parseDouble(nextToken()); }
}