CF1323B.Count Subrectangles

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.

给你一个长度为 $n$ 的数组 $a$ 和一个长度为 $m$ 的数组 $b$，其中每个元素均为 $0$ 或 $1$。考虑一个大小为 $n \times m$ 的矩阵 $c$，其元素按如下规则定义：$c_{i, j} = a_i \cdot b_j$（即 $a_i$ 与 $b_j$ 的乘积）。显然，$c$ 中的元素也仅由 $0$ 和 $1$ 构成。

矩阵 $c$ 中有多少个面积（即单元格总数）恰好为 $k$ 且全部由 $1$ 组成的子矩形？

子矩形是指若干连续行与若干连续列的交集。换言之，给定四个整数 $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$），子矩形 $c[x_1 \dots x_2][y_1 \dots y_2]$ 即为行 $x_1, x_1+1, x_1+2, \dots, x_2$ 与列 $y_1, y_1+1, y_1+2, \dots, y_2$ 的交集。

子矩形的大小（面积）即为其所含单元格的总数。

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$.

第一行包含三个整数 $n$、$m$ 和 $k$（$1 \leq n, m \leq 40\,000$，$1 \leq k \leq n \cdot m$），分别表示数组 $a$ 的长度、数组 $b$ 的长度以及子矩形所需的大小。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq 1$），即数组 $a$ 的元素。

第三行包含 $m$ 个整数 $b_1, b_2, \ldots, b_m$（$0 \leq b_i \leq 1$），即数组 $b$ 的元素。

Output single integer — the number of subrectangles of $c$ with size (area) $k$ consisting only of ones.

输出一个整数——即由全为 1 的元素构成、面积为 $k$ 的子矩形 $c$ 的个数。

In first example matrix $c$ is:

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

In second example matrix $c$ is:

在第一个例子中，矩阵 $c$ 为：

其中包含 $4$ 个大小为 $2$、且仅由数字 $1$ 构成的子矩形：

在第二个例子中，矩阵 $c$ 为：