题目描述

本题中，首先会告诉你 $26$ 个小写英文字母中哪些字母是好的字母，哪些是不好的字母。

然后再给你一个长度不超过 $2000$ 的字符串 $s$，$s$ 仅由小写英文字母组成。

对于 $s$ 的任意一个 非空子串，如果这个子串中包含的不好的字母个数不大于 $k$ 个，则我们称这个子串是一个好的子串。

求：字符串 $s$ 中包含多少个 本质不同的好的子串？

注：我们称两个子串一模一样（不考虑位置），则我们称这两个子串本质相同；如果不一模一样，则这两个子串本质不同。

输入格式

第一行，一个字符串 $s$。

第二行，一个长度恰好为 $26$ 的 01 字符串，其第 $i$ 个字符为 1 说明第 $i$ 个小写英文字母是好的字母，为 0 说明第 $i$ 个小写英文字母是不好的字母。

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

输出格式

输出一个整数，表示字符串 $s$ 中包含的本质不同的好的子串个数。

ababab
01000000000000000000000000
1

5

acbacbacaa
00000000000000000000000000
2

8

说明/提示

数据规模与约定

用 $|s|$ 表示字符串 $s$ 的长度，则

• 对于 $20\%$ 的数据，$|s| \le 20$
• 对于 $50\%$ 的数据，$|s| \le 200$
• 对于 $100\%$ 的数据，$|s| \le 2000, 0 \le k \le |s|$