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 sys
from collections import defaultdict as dd
from collections import deque
from fractions import Fraction as f
def eprint(*args):
    print(*args, file=sys.stderr)
zz=1
from math import *
import copy
#sys.setrecursionlimit(10**6)
if zz:
	input=sys.stdin.readline
else:	
	sys.stdin=open('input.txt', 'r')
	sys.stdout=open('all.txt','w')
def li():
	return [int(x) for x in input().split()]
def fi():
	return int(input())
def si():
	return list(input().rstrip())	
def mi():
	return 	map(int,input().split())	
def gh():
	sys.stdout.flush()
def bo(i):
	return ord(i)-ord('a')
from copy import *
from bisect import *	

from itertools import permutations 



t=1

while t>0:
	t-=1
	n,m,k=mi()
	a=li()
	dd=[]
	i=0
	
	dd=[0 for i in range(min(n,k)+2)]		

	i=0	
	while i<n:
		c=0
		while i<n and a[i]==1:
			c+=1
			i+=1
			dd[1]+=1
			dd[min(c,k)+1]-=1
		if i<n and a[i]==0:
			i+=1
	
	for i in range(1,len(dd)):
		dd[i]+=dd[i-1]		
	b=li()
	d=[0 for i in range(min(m,k)+2)]

	ans=0
	i=c=0
	while i<m:
		c=0
		while i<m and b[i]==1:
			c+=1
			d[1]+=1
			i+=1
			d[min(k,c)+1]-=1
		else:
			i+=1	
	for i in range(1,len(d)):
		d[i]+=d[i-1]
	for i in range(1,len(dd)):
		if k%i==0 and k//i<=m:
			ans+=dd[i]*d[k//i]
	print(ans)	