给定一个长度为 nnn 的数组 aaa 和一个长度为 mmm 的数组 bbb。

两个数组均只包含 000 和 111。

利用两个给定数组生成一个 n×mn×mn×m 的矩阵 ccc，其中 cij=ai×bjc_{ij}=a_i×b_jcij​=ai​×bj​。

显然，矩阵 ccc 中也只包含 000 和 111。

请问，矩阵 ccc 中有多少个大小（面积）恰好为 kkk 且只包含 111 的子矩形？

子矩形是指矩阵中连续若干行和连续若干列的交集。

例如，考虑四个整数 x1,x2,y1,y2(1≤x1≤x2≤n,1≤y1≤y2≤m)x_1,x_2,y_1,y_2(1≤x_1≤x_2≤n,1≤y_1≤y_2≤m)x1​,x2​,y1​,y2​(1≤x1​≤x2​≤n,1≤y1​≤y2​≤m)，子矩形 c[x1…x2][y1…y2]c[x_1…x_2][y_1…y_2]c[x1​…x2​][y1​…y2​] 即为行 x1,x1+1,…,x2x_1,x_1+1,…,x_2x1​,x1​+1,…,x2​ 和列 y1,y1+1,…,y2y_1,y_1+1,…,y_2y1​,y1​+1,…,y2​ 的一个交集。

一个子矩形的大小（面积）等于它包含的数字个数。

输入格式
第一行包含三个整数 n,m,kn,m,kn,m,k。

第二行包含 nnn 个整数 a1,…,ana_1,…,a_na1​,…,an​，表示数组 aaa 中的元素。

第三行包含 mmm 个整数 b1,…,bmb_1,…,b_mb1​,…,bm​，表示数组 bbb 中的元素。

输出格式
输出满足条件的子矩形的总数量。

数据范围
1≤n,m≤40000,1≤n,m≤40000,1≤n,m≤40000,
1≤k≤n×m,1≤k≤n×m,1≤k≤n×m,
0≤ai,bi≤10≤a_i,b_i≤10≤ai​,bi​≤1

输入样例1：

3 3 2
1 0 1
1 1 1

输出样例1：

4

输入样例2：

3 5 4
1 1 1
1 1 1 1 1

输出样例2：

14

样例解释
对于样例 111，矩阵 ccc 如下：

共有 4 个面积为 2 且只包含 1 的子矩形，如下：

对于样例 2，矩形 c 如下：

1. 矩形面积为 kkk，可以枚举一个边 (a,b)(a, b)(a,b)
2. 可以发现求面积为 kkk 的 111 的矩形个数，相当于求 (AAA 中有多少个连续的 111 长度为 aaa) ✖ (BBB 中有多少个连续的 111 长度为 bbb)
3. 用 sss 数组距离长度为 iii 的 111 的个数，s[i]s[i]s[i] 表示有 s[i]s[i]s[i] 个(连续的 111)长度为 iii
4. 当 AAA 中有连续的 111 长度为 ttt，它对 sss 数组 [1[1[1~t]t]t] 都有个为 111 的贡献(相当于给 s[1s[1s[1~t]t]t] 都加{可以用差分数组处理})

#includeusing namespace std;typedef long long LL;const int N = 40010;int n, m, k;
int a[N], b[N];
int s1[N], s2[N];void work(int w[], int s[], int n){int j = 0;for(int i = 0; i < n; i++)if(w[i] == 1){j++;s[1]++;s[j + 1]--;}else j = 0;for(int i = 1; i <= n; i++) s[i] += s[i-1];
}int main(){scanf("%d%d%d", &n, &m, &k);for(int i = 0; i < n; i++) scanf("%d", &a[i]);for(int i = 0; i < m; i++) scanf("%d", &b[i]);work(a, s1, n);work(b, s2, m);LL res = 0;for(int i = 1; i <= n; i++){if(k % i) continue;int j = k / i;if(j > m) continue;res += s1[i] * s2[j];}printf("%lld\n", res);return 0;
}