AT_toyota2023spring_final_a Area Sum

有一个由 $N$ 行 $M$ 列组成的棋盘，每个格子中按照行优先顺序写有 $1$ 到 $N \times M$ 的整数。也就是说，记从上到下第 $i$ 行、从左到右第 $j$ 列的格子中的整数为 $A_{i,j}$，则有 $A_{i,j} = (i-1) \times M + j$。 请统计这个棋盘中有多少个子矩形，其内部所有格子的数之和恰好等于 $V$。 更严格地说，请统计满足以下条件的整数四元组 $(a, b, c, d)$ 的个数：$1 \leq a \leq b \leq N$，$1 \leq c \leq d \leq M$，且 $$ \sum_{a \leq i \leq b,\, c \leq j \leq d} A_{i,j} = V $$ 成立。

输入从标准输入中给出，格式如下： > $N$ $M$ $V$

输出答案。

### 限制条件 - $1 \leq N, M \leq 5000$ - $1 \leq V \leq 10^{15}$ - 输入的所有数均为整数 ### 样例解释 1 棋盘上的整数如下所示： ``` 1 2 3 4 ``` 满足条件的子矩形有 $(a, b, c, d) = (1, 1, 1, 2), (2, 2, 1, 1)$ 共 $2$ 个。 由 ChatGPT 4.1 翻译