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, stdout
def main():
    #t=int(input())
    t=1
    for x in range(t):
        n,m,k=map(int,input().split())
        a=list(map(int,input().split()))
        b=list(map(int,input().split()))
       
        l=[]
        c=0
        for i in range(m):
            if b[i]==1:
                c+=1
            else:
                if c!=0:
                    l.append(c)
                c=0
        if c!=0:
            l.append(c)
        lr=[]
        c=0
        for i in range(n):
            if a[i]==1:
                c+=1
            else:
                if c!=0:
                    lr.append(c)
                c=0
        if c!=0:
            lr.append(c)
        rep1=0
        ans=0
        for i in l:
            if i>=k:
                ans+=(i-k+1)
        rep1=sum(l[:])
        len_l=len(l)
        rep=ans 
        #print(1,ans)
        ans=0 
        for i in a:
            if i!=0:
                ans+=rep
        #print(ans)
        if k%2!=0:
            if k!=1:
                for i in lr:
                    if i>=k:
                        ans+=(rep1*(i-(k-1)))
        else:
            #print(1,l)
            repet={}
            maxi=0
            if len(lr)>0:
                maxi=max(lr[:])
            for j in range(2,min(maxi+1,k//2+1)):
                if k%j==0:
                    for i in l:
                        if i>=k//j:
                            repet[k//j]=repet.get(k//j,0)+(i-k//j+1)
                    #print(2,repet[k//j],k//j)
            #print(repet)    
            cnt=0
            add=0
            rev=0
            #print(repet)
            for i in range(n):
                if a[i]==1:
                    cnt+=1
                    if cnt>=2:
                        if cnt>=k:
                            add=rep1
                            #print("add",add,rev,cnt)
                            ans+=(add+rev)
                        else:    
                            if k%cnt==0 and cnt!=k :
                                rev+=repet.get(k//cnt,0)
                                ans+=(add+rev)
                                
                                #print("add",add,rev,cnt)
                                #print(cnt,add,rev)
                                add=0
                            else:
                                #print(cnt,add,rev)
                                #print("add",add,rev,cnt)
                                ans+=(rev+add)
                                add=0
                            
                else:
                    cnt=0
                    rev=0
                    add=0
        print(ans)
if __name__ == "__main__": 
    main()      