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>
# https://codeforces.com/problemset/problem/1323/B

n,m,k = list(map(int,input().strip().split()))
arr_n = list(map(int,input().strip().split()))
arr_m = list(map(int,input().strip().split()))

rec_n = []
rec_m = []

temp_count = 0
for i in range(n):
    if arr_n[i]==0:
        if temp_count!=0:
            rec_n.append(temp_count)
            temp_count = 0
    else:
        temp_count+=1
else:
    if temp_count:
        rec_n.append(temp_count)

temp_count = 0

for i in range(m):
    if arr_m[i]==0:
        if temp_count!=0:
            rec_m.append(temp_count)
            temp_count = 0
    else:
        temp_count+=1
else:
    if temp_count:
        rec_m.append(temp_count)


import math

def getDivisors(n):
    i = 1
    divisors = []
    while i <= math.sqrt(n):
        if (n % i == 0):
            divisors.append((i,n//i))
            if n//i != i:
                divisors.append((n//i,i))
        i = i + 1
    return divisors

div_k = getDivisors(k)
div_k = sorted(div_k,key=lambda x: x[0])
div_1, div_2 = zip(*div_k)
len_div = len(div_1)

from bisect import bisect_right

def count_subrect(n,m):
    global div_1,div_2,len_div
    i1 = bisect_right(div_1,n)
    ans = 0
    for i in range(i1):
        l1 = div_1[i]
        l2 = div_2[i]
        if l2>m:
            continue
        ans+=(n-l1+1)*(m-l2+1)
    return ans 

from collections import Counter 

rec_n = Counter(rec_n)
rec_m = Counter(rec_m)

# print(rec_n)
# print(rec_m)

final_ans = 0
for i in rec_n.keys():
    for j in rec_m.keys():
        final_ans+= count_subrect(i,j)*rec_n[i]*rec_m[j]

print(final_ans)