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.*;

public class tr0 {
	static PrintWriter out;
	static StringBuilder sb;
	static int mod = 1000000007;
	static int inf = (int) 1e15;
	static ArrayList<Integer>[] ad;
	static int n, s;
	static int[][][] memo;
	static int[] a;

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		out = new PrintWriter(System.out);
		n = sc.nextInt();
		int m = sc.nextInt();
		long k = sc.nextInt();
		int[] a = sc.nextArrInt(n);
		int[] b = sc.nextArrInt(m);
		long ans = 0;
		ArrayList<Integer> cona = new ArrayList<>();
		ArrayList<Integer> conb = new ArrayList<>();
		ArrayList<Integer> div = new ArrayList<>();
		for (long i = 1; i * i <= k; i++) {
			if (k % i != 0)
				continue;
			if (i == k / i)
				div.add((int) i);
			else {
				div.add((int) i);
				div.add((int) (k / i));
			}
		}
		for (int i = 0; i < n; i++) {
			int num = 0;
			while (i < n && a[i] == 1) {
				i++;
				num++;
			}
			if (num != 0)
				cona.add(num);
		}
		for (int i = 0; i < m; i++) {
			int num = 0;
			while (i < m && b[i] == 1) {
				i++;
				num++;
			}
			if (num != 0)
				conb.add(num);
		}
		Collections.sort(cona);
		Collections.sort(conb);
		Collections.reverse(cona);
		Collections.reverse(conb);
		Collections.sort(div);
		int[][] pre = new int[div.size()][conb.size()];
		int id = 0;
		HashMap<Integer, Integer> hm = new HashMap<>();
		for (int d : div) {
			int ib = 0;
			hm.put(d, id);
			for (int bb : conb) {
				pre[id][ib++] = (bb + 1 - d);
			}
			for (int y = 1; y < ib; y++)
				pre[id][y] += pre[id][y - 1];
			id++;
		}
		for (int d : div) {
			for (int aa : cona) {
				if (aa < d)
					break;
				int y = (int) k / d;
				int lo = 0;
				int hi = conb.size() - 1;
				int aaa = -1;
				while (lo <= hi) {
					int mid = (lo + hi) >> 1;
					if (conb.get(mid) < y) {
						hi= mid - 1;
					} else {
						lo = mid + 1;
						aaa = mid;
					}
				}
				if (aaa != -1)
					ans += (((long) pre[hm.get(y)][aaa]) * 1l * (aa + 1 - d));
			}
		}
		System.out.println(ans);
		out.close();
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}

		public Scanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}

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

		public String nextLine() throws IOException {
			return br.readLine();
		}

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

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

		public char nextChar() throws IOException {
			return next().charAt(0);
		}

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

		public int[] nextArrInt(int n) throws IOException {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		public long[] nextArrLong(int n) throws IOException {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
}
