题目描述

有一个只包含小写字母，长度为 $n$ 的字符串 $S$ 。有一些字母是好的，剩下的是坏的。

定义一个子串 $S_{l\ldots r}$是好的，当且仅当这个子串包含不超过 $k$ 个坏的字母。

求有多少个不同的满足以下要求的字符串 $T$ ：

• $T$ 作为 $S$ 的子串出现过。
• 存在一个 $T$ 出现的位置 $[l,r]$ ，满足 $S_{l\ldots r}$ 是好的。

输入格式

第一行有一个字符串 $S$ 。

第二行有一个字符串 $B$ 。若 $B_i=$'1' 则表示 $S_i$ 是好的，否则表示 $S_i$ 是坏的。

第三行有一个整数 $k$ 。

输出格式

一个整数：答案。

样例

样例一

input

ababab
010101
1

output

5

explanation

所有'b'是好的，'a'是坏的。

满足条件的字符串有："a","ab","b","ba","bab"。

样例二

input

ababab
100000
1

output

3

explanation

$S_1$ 是好的，其他的字符都是坏的。

满足条件的字符串有："a","ab","b"。

虽然 $S_{3\ldots4}=S_{5\ldots6}=$"ab" 是坏的，但是这并不影响 "ab" 满足条件，因为 $S_{1\ldots2}=$"ab" 是好的。

数据范围与提示

子任务 $1$（$10$ 分）：$n\leq 10$。

子任务 $2$（$10$ 分）：$n\leq 100$。

子任务 $3$（$10$ 分）：$n\leq 1000$。

子任务 $4$（$10$ 分）：$n\leq 100000,k=n$。

子任务 $5$（$10$ 分）：$n\leq 100000,k=0$。

子任务 $6$（$20$ 分）：$n\leq 100000$，若$S_i=S_j$，则$B_i=B_j$。

子任务 $7$（$30$ 分）：$n\leq 100000$。

对于 $100\%$ 的数据：$1\leq n\leq {10}^5,0\leq k\leq {10}^5$， $S$ 只包含小写字母。

题目来源：全是水题的GDOI模拟赛 by yww