单点时限: 5.0 sec
内存限制: 512 MB
有两个无限长的字符串 $s$, $t$，周期分别为 $n$, $m$：
周期的定义如下：字符串 $s$ 的周期为 $n$，则字符串 $s$ 满足 $s[1..n]=s[n+1..2n]=s[dn+1..(d+1)n]$, 对于 $d \ge 0$。其中 $s[i..j]$ 表示 $s$ 从第 $i$ 个字符到第 $j$ 个字符的子串。
现求满足 $1 \le i \le k$ 且 $s_i=t_i$ 的 $i$ 的个数。亦即，两个字符串前 $k$ 个位置有多少位置是相等的？
第一行三个整数 $n, m, k$ ($1 \le n,m \le 125~512, 1 \le k \le 10^{18}$)。
第二行，长度为 $n$ 的字符串 $s$。
第三行，长度为 $m$ 的字符串 $t$。
$s$, $t$ 均由 AGCT 组成。
5 4 9 AGCAG AGCC
5
5 4 9 AAAAA AAAA
9