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.util.Map.Entry;
import java.util.concurrent.CountDownLatch;

import javax.security.auth.kerberos.KerberosKey;
import javax.swing.plaf.basic.BasicInternalFrameTitlePane.MaximizeAction;

import org.omg.PortableServer.AdapterActivator;

import java.math.*;
import java.io.*;
import java.lang.reflect.Constructor;

public class Main {
	static long INF = Long.MAX_VALUE;

	public static void main(String[] args) throws FileNotFoundException {
		InputReader in = new InputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);
		// InputReader in = new InputReader(new
		// File("ethan_traverses_a_tree.txt"));
		// PrintWriter out = new PrintWriter(new
		// File("ethan_traverses_a_tree-output.txt"));

		int n = in.nextInt();
		int m = in.nextInt();
		int 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();
		}

		Map<Integer, Integer> mapa = arrToMap(a, n);
		Map<Integer, Integer> mapb = arrToMap(b, m);

		long ans = 0;
		for (int i = 1; i * i <= k; i++) {
			if (k % i == 0) {
				int v1 = i;
				int v2 = k / i;
				//System.out.println(v1 + " " + v2);
				
				ans = ans + getCount(mapa, mapb, v1, v2);
				if(v1 != v2) {
					ans = ans + getCount(mapa, mapb, v2, v1);
				}
			}
		}
		out.printf("%d\n", ans);

		out.close();
	}

	static Map<Integer, Integer> arrToMap(int[] a, int n) {
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		int count = 0;
		for (int i = 0; i < n; i++) {
			if (a[i] == 0) {
				if (map.containsKey(count) == false) {
					map.put(count, 0);
				}
				map.put(count, map.get(count) + 1);
				count = 0;
			} else {
				count++;
			}
		}
		if (map.containsKey(count) == false) {
			map.put(count, 0);
		}
		map.put(count, map.get(count) + 1);
		count = 0;
		return map;
	}

	static long getCount(Map<Integer, Integer> map1, Map<Integer, Integer> map2, int v1, int v2) {
		long count1 = 0;
		for (Map.Entry<Integer, Integer> entry : map1.entrySet()) {
			int key = entry.getKey();
			int value = entry.getValue();
			if (key >= v1) {
				count1 = count1 + (long) (key - v1 + 1) * value;
			}
		}
		long count2 = 0;
		for (Map.Entry<Integer, Integer> entry : map2.entrySet()) {
			int key = entry.getKey();
			int value = entry.getValue();
			if (key >= v2) {
				count2 = count2 + (long) (key - v2 + 1) * value;
			}
		}
		return count1 * count2;
	}

	static class InputReader {
		BufferedReader br;
		StringTokenizer st;

		public InputReader(File f) {
			try {
				br = new BufferedReader(new FileReader(f));
			} catch (FileNotFoundException e) {
				e.printStackTrace();
			}
		}

		public InputReader(InputStream in) {
			br = new BufferedReader(new InputStreamReader(in));
		}

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

		public boolean hasNext() {
			while (st == null || !st.hasMoreTokens()) {
				String s = null;
				try {
					s = br.readLine();
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (s == null)
					return false;
				st = new StringTokenizer(s);
			}
			return true;
		}

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

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

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