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>
from sys import stdin
from collections import *


def factorize(n):  # o(sqr(n))
    c, ans = 1, []
    while (c * c < n):
        if n % c == 0:
            ans.extend([c, n // c])
        c += 1

    if c * c == n:
        ans.append(c)
    return sorted(ans)


def arr_inp(n):
    if n == 1:
        return [int(x) for x in stdin.readline().split()]
    elif n == 2:
        return [float(x) for x in stdin.readline().split()]
    else:
        return list(stdin.readline()[:-1])


def row(arr, l):
    tem, tem2 = 0, []
    for i in range(l):
        if arr[i]:
            tem += 1
        else:
            if tem:
                tem2.append(tem)
            tem = 0
    if tem:
        tem2.append(tem)
    return sorted(tem2)


def cum():
    mem, tem, tem1 = Counter(c), [0], [0]
    for i in range(1, c[-1] + 1):
        tem.append(tem[-1] + mem[i])
        tem1.append(tem1[-1] + mem[i] * i)

    return tem, tem1


n, m, k = arr_inp(1)
a, b, ans = arr_inp(1), arr_inp(1), 0
r, c, facs = row(b, m), row(a, n), factorize(k)

if c:
    sum1, cu = cum()

    for i in range(len(facs)):
        r1, c1 = facs[i], facs[-(i + 1)]

        for j in r:
            if c[-1] >= c1:
                ans += max(j - r1 + 1, 0) * max(0, (cu[-1] - cu[c1 - 1]) - ((sum1[-1] - sum1[c1 - 1]) * (c1 - 1)))

print(ans)
