题目内容

给定两个仅包含小写字符 $a$ 和 $b$ 的字符串 $A$ 和 $B$ ，长度分别为 $n$ 和 $m$ ，现在根据 $A$ 和 $B$ 构造一个 $n*m$ 的字符矩阵 $C$ ，其中 $C_{ij}$ 的值由 $A_i$ 和 $B_j$ 决定，具体计算方式如下:

• 如果 $A_i$ 和 $B_j$ 都为 $a$ ，则 $C_{ij}$ 为 $a$ ;

• 否则 $C_{ij}$ 为 $b$ 。

多多对字符 $a$ 情有独钟，他想知道矩阵 $C$ 中共有多少个仅包含 $a$ 的子矩形，并且其字符总数恰好为 $k$ ?

输入描述

三行，第一行三个正整数 $n,m,k$ ，分别表示字符串 $A$ 和 $B$ 的长度，以及多多想知道的子矩形个数。

第二行为字符串 $A$

第三行为字符串 $B$

$(1<= n,m <= 1000,000,1 <= k<= n*m)$

输出描述

一个整数 $k$

样例1

输入

3 3 2
aaa
aba

输出

4

说明

由 $A$ 和 $B$ 构成的矩形 $C$ 为

$aba$

$aba$

$aba$

所以有四个子矩形全都为 $a$

样例2

输入

3 6 4
aaa
aaaaaa

输出

19