题目描述

有一个只包含小写字母，长度为 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 。

输出格式

一个整数：答案。

样例

样例一

ababab
010101
1

5

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

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

样例二

ababab
100000
1

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