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 \times m$ formed by following rule: $c_{i, j} = a_i \cdot 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 \le x_1 \le x_2 \le n$, $1 \le y_1 \le y_2 \le m$) a subrectangle $c[x_1 \dots x_2][y_1 \dots y_2]$ is an intersection of the rows $x_1, x_1+1, x_1+2, \dots, x_2$ and the columns $y_1, y_1+1, y_1+2, \dots, 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 \leq n, m \leq 40\,000, 1 \leq k \leq n \cdot m$), length of array $a$, length of array $b$ and required size of subrectangles.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 1$), elements of $a$.

The third line contains $m$ integers $b_1, b_2, \ldots, b_m$ ($0 \leq b_i \leq 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:

 $\left(\begin{array}{l l l}{1} & {1} & {1} \\{0} & {0} & {0} \\{1} & {1} & {1} \end{array} \right)$ 

There are $4$ subrectangles of size $2$ consisting of only ones in it:

 [Image] 

In second example matrix $c$ is:

 $\left(\begin{array}{l l l l l}{1} & {1} & {1} & {1} & {1} \\{1} & {1} & {1} & {1} & {1} \\{1} & {1} & {1} & {1} & {1} \end{array} \right)$

Difficulty: interview

Starter code:

Solutions:
from collections import Counter
from itertools import product
n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
a1 = [0]
b1 = [0]
for i in range(n):
  if a[i] == 1:
    a1[-1] += 1
  elif a1[-1] != 0:
    a1.append(0)
for i in range(m):
  if b[i] == 1:
    b1[-1] += 1
  elif b1[-1] != 0:
    b1.append(0)
pr = []
for i in range(1,int(k**0.5)+1):
  if k%i == 0 and k//i <= 40000:
    pr.append((i,k//i))
    if i != k//i:
      pr.append((k//i,i))
ca = Counter(a1)
cb = Counter(b1)
ans = 0
for i,j in product(ca.items(),cb.items()):
  for x,y in pr:
    if i[0] >= x and j[0] >= y:
      ans += i[1]*j[1]*(i[0]-x+1)*(j[0]-y+1)
print(ans)

def count(A):
    segs = []
    cur = 0
    flag = 0
    for a in A:
        if a:
            cur += 1
            flag = 1
        else:
            if flag:
                flag = 0
                segs.append(cur)
                cur = 0
    if flag and (cur > 0):
        segs.append(cur)
    count = [0]*(len(A)+1)
    for s in segs:
        for i in range(1,s+1):
            count[i] += (s-i+1)
    # print(count)
    return count

def f():
    n, m, k = [int(s) for s in input().split()]
    A = [int(s) for s in input().split()]
    B = [int(s) for s in input().split()]
    ans = 0
    countA = count(A)
    countB = count(B)
    for l1 in range(1,n+1):
        if k%l1:
            continue
        l2 = k//l1
        if l2 > m:
            continue
        ans += countA[l1]*countB[l2]
    print(ans)

f()

n,m,k=map(int,input().split())
a=input().split()
b=input().split()
ans=0
for i in range(1,int(k**0.5)+1):
    if(k%i==0):
        f1=i
        f2=k//i
        if(f1!=f2):
            temp1=0
            count=0
            for j in range(n):
                if(a[j]=='1'):
                    count+=1
                else:
                    count=0
                if(count>=f1):
                    temp1+=1
            temp2=0
            count=0
            for j in range(m):
                if(b[j]=='1'):
                    count+=1
                else:
                    count=0
                if(count>=f2):
                    temp2+=1
            #print(f1,f2,temp1,temp2)        
            ans+=temp1*temp2
            temp1=0
            count=0
            for j in range(n):
                if(a[j]=='1'):
                    count+=1
                else:
                    count=0
                if(count>=f2):
                    temp1+=1
            temp2=0
            count=0
            for j in range(m):
                if(b[j]=='1'):
                    count+=1
                else:
                    count=0
                if(count>=f1):
                    temp2+=1
            ans+=temp1*temp2
            #print(f1,f2,temp1,temp2)   
        else:
            temp1=0
            count=0
            for j in range(n):
                if(a[j]=='1'):
                    count+=1
                else:
                    count=0
                if(count>=f1):
                    temp1+=1
            temp2=0
            count=0
            for j in range(m):
                if(b[j]=='1'):
                    count+=1
                else:
                    count=0
                if(count>=f2):
                    temp2+=1
            ans+=temp1*temp2
            #print(f1,f2,temp1,temp2)   
print(ans)            

import sys
from collections import defaultdict
n,m,k=list(map(int,sys.stdin.readline().split()))
a=list(map(int,sys.stdin.readline().split()))
b=list(map(int,sys.stdin.readline().split()))
consa=defaultdict(int)
consb=defaultdict(int)
count=0
arra=set()
arrb=set()
for i in range(n):
    if a[i]==1:
        count+=1
        arra.add(count)
        consa[count]+=1
    else:
        count=0
count=0
for i in range(m):
    if b[i]==1:
        count+=1
        arrb.add(count)
        consb[count]+=1
    else:
        count=0
arra=list(arra)
arrb=list(arrb)
arra.sort()
arrb.sort()
arra.reverse()
arrb.reverse()
prev=0
for i in arra:
    consa[i]+=prev
    prev=consa[i]
prev=0
for i in arrb:
    consb[i]+=prev
    prev=consb[i]
#print(consa,'consa')
#print(consb,'consb')
ans=0
vis=defaultdict(int)
for i in range(1,n+1):
    if k%i==0:
        ans+=consa[i]*consb[k//i]
        vis[k//i]+=1
for i in range(1,m+1):
    if k%i==0 and vis[i]==0:
        ans+=consb[i]*consa[k//i]
print(ans)


N,M,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
pA=[0]*(N+1)
for i in range(N):
    pA[i+1]=pA[i]+A[i]
pB=[0]*(M+1)
for i in range(M):
    pB[i+1]=pB[i]+B[i]
ans=0
for p in range(1,int(K**0.5)+1):
    if K%p>0: continue
    q=K//p
    if p>q: break

    X=0
    for i in range(N+1-p):
        if pA[i+p]-pA[i]==p: X+=1
    Y=0
    for i in range(M+1-q):
        if pB[i+q]-pB[i]==q: Y+=1
    ans+=X*Y
    if p==q: break
    X=0
    for i in range(N+1-q):
        if pA[i+q]-pA[i]==q: X+=1
    Y=0
    for i in range(M+1-p):
        if pB[i+p]-pB[i]==p: Y+=1
    ans+=X*Y
print(ans)

from math import sqrt
n, m, k = list(map(int, input().split()))

a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]

ac = [0] * (n + 1)
bc = [0] * (m + 1)

cs = 0

for ai in a:
    if ai == 1:
        cs += 1
    if ai == 0:
        ac[cs] += 1
        cs = 0
ac[cs] += 1

cs = 0
for bi in b:
    if bi == 1:
        cs += 1
    if bi == 0:
        bc[cs] += 1
        cs = 0
bc[cs] += 1

pairs = []

for i in range(1, int(sqrt(k) + 1)):
    if k % i == 0:
        pairs.append((i, k // i))

total = 0

for i, j in pairs:
    if i <= n and j <= m:
        act = 0
        for k in range(i, n + 1):
            act += ac[k] * (k - i + 1)
        bct = 0
        for k in range(j, m + 1):
            bct += bc[k] * (k - j + 1)

        total += act * bct
    if j <= n and i <= m and i != j:
        act = 0
        for k in range(j, n + 1):
            act += ac[k] * (k - j + 1)
        bct = 0
        for k in range(i, m + 1):
            bct += bc[k] * (k - i + 1)

        total += act * bct

print(total)


from sys import stdin
from collections import defaultdict
input = stdin.readline

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

n_map = [0] * (n + 1)
m_map = [0] * (m + 1)

l1 = list(map(int, input().split()))
l2 = list(map(int, input().split()))

count = 0
for elem in l1:
    if elem == 0:
        count = 0
    else:
        count += 1
        n_map[count] += 1

count = 0
for elem in l2:
    if elem == 0:
        count = 0
    else:
        count += 1
        m_map[count] += 1

for idx in range(n-1, -1, -1):
    n_map[idx] += n_map[idx+1]
for idx in range(m-1, -1, -1):
    m_map[idx] += m_map[idx+1]

count = 0
for i in range(1, n+1):
    if k % i or k//i >= len(m_map):
        continue
    count += m_map[k//i] * n_map[i]
print(count)


#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import bisect

def divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

n, m, k = map(int, input().split())
a = [int(item) for item in input().split()] + [0]
b = [int(item) for item in input().split()] + [0]

acnt = []
bcnt = []
c = 0
for item in a:
    if item == 1:
        c += 1
    else:
        acnt.append(c)
        c = 0
c = 0
for item in b:
    if item == 1:
        c += 1
    else:
        bcnt.append(c)
        c = 0
acnt.sort()
bcnt.sort()

ans = 0
div = divisors(k)
for a_val in div:
    b_val = k // a_val
    a_idx = bisect.bisect_left(acnt, a_val)
    b_idx = bisect.bisect_left(bcnt, b_val)
    a_total = sum(acnt[a_idx:]) - (len(acnt) - a_idx) * (a_val - 1)
    b_total = sum(bcnt[b_idx:]) - (len(bcnt) - b_idx) * (b_val - 1)
    ans += a_total * b_total

print(ans)

# -*- coding: utf-8 -*-
import bisect
# import heapq
# import math
# import random
import sys
from collections import Counter
# from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
# from functools import lru_cache, reduce
# from itertools import combinations, combinations_with_replacement, product, permutations
# from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def divisor(n):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            yield i
            if i != n // i:
                yield n // i


@mt
def slv(N, M, K, A, B):
    ans = 0
    ca = [0]
    for v in A:
        if v == 1:
            ca[-1] += 1
        else:
            ca.append(0)
    cb = [0]
    for v in B:
        if v == 1:
            cb[-1] += 1
        else:
            cb.append(0)
    ca = Counter(ca)
    cb = Counter(cb)
    ans += 0
    for d in divisor(K):
        e = K//d
        for i, x in ca.items():
            for j, y in cb.items():
                if i < d or j < e:
                    continue
                ans += ((i-d+1) * (j-e+1)) * x * y
    return ans


def main():
    N, M, K = read_int_n()
    A = read_int_n()
    B = read_int_n()
    print(slv(N, M, K, A, B))

    # N = 40000
    # M = 40000
    # K = random.randint(1, N*M)
    # K =10
    # A = random.choices([0, 1], k=N)
    # B = random.choices([0, 1], k=M)
    # print(slv(N, M, K, A, B))



def __starting_point():
    main()

__starting_point()

import sys
input = sys.stdin.readline
n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
scale = 40000
#scale = 10
ca = [0 for _ in range(scale+1)]
cb = [0 for _ in range(scale+1)]
now = 0
for x in a:
  if x:
    now += 1
  else:
    now = 0
  ca[now] += 1
now = 0
for x in b:
  if x:
    now += 1
  else:
    now = 0
  cb[now] += 1
#print(ca)
#print(ca)
for i in range(scale)[::-1]:
  ca[i] += ca[i+1]
  cb[i] += cb[i+1]
#print(ca)
#print(cb)
ans = 0
roo = int(k**.5)
for i in range(1,roo+1):
  if k % i == 0 and k // i <= scale:
    ans += ca[i] * cb[k//i]
    ans += cb[i] * ca[k//i]
if roo ** 2 == k:
  ans -= ca[roo] * cb[roo]
print(ans)

import sys
input=sys.stdin.readline
from math import sqrt
from collections import defaultdict as dd
n,m,k=list(map(int,input().split()))
l1=list(map(int,input().split()))
l2=list(map(int,input().split()))
cou=0
d1=dd(int)
for i in range(n):
    if(l1[i]):
        cou+=1
    else:
        cc=cou
        for j in range(1,cou+1):
            d1[j]+=cc
            cc-=1
        cou=0
cc=cou
for j in range(1,cou+1):
    d1[j]+=cc
    cc-=1
cou=0

d2=dd(int)
cou=0
for i in range(m):
    if(l2[i]):
        cou+=1
    else:
        cc=cou
        for j in range(1,cou+1):
            d2[j]+=cc
            cc-=1
        cou=0
cc=cou
for j in range(1,cou+1):
    d2[j]+=cc
    cc-=1
cou=0
sk=int(sqrt(k))
su=0
#print(d1,d2)
for i in range(1,sk+1):
    if(k%i==0):
        su+=d1[i]*d2[k//i]
        if(i!=k//i):
            su+=d1[k//i]*d2[i]
print(su)


# import sys

# sys.stdin = open('test')


def get_dividers(k):
    dividers = set()
    for i in range(1, int(k ** 0.5) + 2):
        if k % i == 0:
            dividers.add(i)
            dividers.add(k // i)

    return sorted(list(dividers))


n, m, k = map(int, input().split())
dividers = get_dividers(k)
A = list(map(int, input().split()))
B = list(map(int, input().split()))



def count(A, d):
    in_a_row = 0
    res = 0
    for a in A:
        if a == 1:
            in_a_row += 1
            if in_a_row >= d:
                res += 1
        else:
            in_a_row = 0
    return res


a_d = {}
b_d = {}
for d in dividers:
    a_d[d] = count(A, d)
    b_d[d] = count(B, d)

res = 0
for d in dividers:
    res += a_d[d] * b_d[k//d]
    # res += b_d[d] * a_d[k//d]
    # print(d, a_d[d] * b_d[k//d], b_d[d] * a_d[k//d], res)
print(res)