仅含 a 的子矩形计数

题目描述

给定两个仅包含小写字符 a 和 b 的字符串 $A$（长度为 $n$）和 $B$（长度为 $m$）。

根据这两个字符串，我们构造一个 $n \times m$ 的字符矩阵 $C$。矩阵中第 $i$ 行第 $j$ 列的字符 $C_{i,j}$ 的生成规则如下：

你的任务是，计算矩阵 $C$ 中有多少个子矩形，满足以下两个条件：

1. 该子矩形内所有字符都是 a。
2. 该子矩形的面积（即包含的字符总数）恰好为 $k$。

输入格式

第一行包含三个正整数 $n, m, k$，分别表示字符串 $A$ 的长度、字符串 $B$ 的长度以及目标子矩形面积。

第二行为字符串 $A$。

第三行为字符串 $B$。

输出格式

输出一个整数，表示满足条件的子矩形数量。

样例

样例输入 1

3 3 2
aaa
aba

样例输出 1

4

样例输入 2

3 6 4
aaa
aaaaaa

样例输出 2

19

提示

样例 1 说明

由 $A=\text{`aaa`}$ 和 $B=\text{`aba`}$ 构成的矩阵 $C$ 如下：

a b a
a b a
a b a

我们需要寻找面积为 $k=2$ 且全为 a 的子矩形。可能的尺寸为 $1 \times 2$ 或 $2 \times 1$。

• 不存在 $1 \times 2$ 的全 a 子矩形。
• 在第 1 列，可以找到 2 个 $2 \times 1$ 的全 a 子矩形。
• 在第 3 列，可以找到 2 个 $2 \times 1$ 的全 a 子矩形。 总计 $2 + 2 = 4$ 个。

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1 \le n, m \le 10^6$
• $1 \le k \le n \times m$
• 字符串 $A$ 和 $B$ 仅由小写字母 a 和 b 构成。