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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main
{
	public static void main(String[] args)
	{
		new Thread(null, new Runnable() {
			public void run() {
                solve();
            }
        }, "1", 1 << 26).start();
	}
	static void solve () {
		FastReader fr =new FastReader();	PrintWriter op =new PrintWriter(System.out);
 
 		int n =fr.nextInt() ,m =fr.nextInt() ,K =fr.nextInt() ,a[] =new int[n] ,b[] =new int[m] ,i ,j ,k ;
 		for (i =0 ; i<n ; ++i)	a[i] =fr.nextInt() ;	for (i =0 ; i<m ; ++i)	b[i] =fr.nextInt() ;

 		long rct[] =new long[40001] ,cct[] =new long[40001] ,c ,d ,ans =0l ;
 		for (j =0 ; j<n ; ++j) {
 			if (a[j]==1) {
 				i =j ;	while (i<n && a[i]==1)	++i ;
 				rct[(i-j)]++ ;	j =i ;
 			}
 		}
 		for (j =0 ; j<m ; ++j) {
 			if (b[j]==1) {
 				i =j ;	while (i<m && b[i]==1)	++i ;
 				cct[(i-j)]++ ;	j =i ;
 			}
 		}
 		c =rct[n] ;
 		for (i =n-1 ; i>0 ; --i) {
 			d =rct[i] ;
 			rct[i] += rct[i+1] ;	rct[i] += c ;
 			c += d ;
 		}
 		//for (i =0 ; i<=n ; ++i)	System.out.println(rct[i]) ;
 		c =cct[m] ;
 		for (i =m-1 ; i>0 ; --i) {
 			d =cct[i] ;
 			cct[i] += cct[i+1] ;	cct[i] += c ;
 			c += d ;
 		}
 		for (i =1 ; i*i<=K ; ++i) {
 			if (K%i != 0)	continue ;	j =K/i ;	if (j>40000)	continue;
 			ans += (rct[i] * cct[j]) ;	
 			if (i!=j)	ans += (rct[j] * cct[i]) ;
 		}
 		op.println(ans) ;	op.flush();	op.close();
	}
	static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br =new BufferedReader(new InputStreamReader(System.in));
		}

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

		String nextLine() {
			String str ="";

			try
			{
				str =br.readLine();
			}
			catch(IOException e)
			{
				e.printStackTrace();
			}

			return str;
		}

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

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