CF271D.Good Substrings

You've got string s, consisting of small English letters. Some of the English letters are good, the rest are bad.

A substring s[l...r] (1 ≤ l ≤ r ≤ |s|) of string s  =  _s_1_s_2...s|s| (where |s| is the length of string s) is string  s__l__s__l + 1...s__r.

The substring s[l...r] is good, if among the letters  s__l, s__l + 1, ..., s__r there are at most k bad ones (look at the sample's explanation to understand it more clear).

Your task is to find the number of distinct good substrings of the given string s. Two substrings s[x...y] and s[p...q] are considered distinct if their content is different, i.e. s[x...y] ≠ s[p...q].

你有一个由小写英文字母组成的字符串 $s$。其中某些英文字母是“好”的，其余的是“坏”的。

字符串 $s = s_1 s_2 \dots s_{|s|}$（其中 $|s|$ 表示字符串 $s$ 的长度）的一个子串 $s[l\dots r]$（满足 $1 \le l \le r \le |s|$）定义为字符串 $s_l s_{l+1} \dots s_r$。

子串 $s[l\dots r]$ 被称为“好”的，当且仅当在字母 $s_l, s_{l+1}, \dots, s_r$ 中，“坏”字母的个数至多为 $k$（参见样例解释以获得更清晰的理解）。

你的任务是求出给定字符串 $s$ 中本质不同的“好”子串的个数。两个子串 $s[x\dots y]$ 和 $s[p\dots q]$ 被视为不同的，当且仅当它们的内容不同，即 $s[x\dots y] \ne s[p\dots q]$。

The first line of the input is the non-empty string s, consisting of small English letters, the string's length is at most 1500 characters.

The second line of the input is the string of characters "0" and "1", the length is exactly 26 characters. If the i-th character of this string equals "1", then the i-th English letter is good, otherwise it's bad. That is, the first character of this string corresponds to letter "a", the second one corresponds to letter "b" and so on.

The third line of the input consists a single integer k (0 ≤ k ≤ |s|) — the maximum acceptable number of bad characters in a good substring.

输入的第一行是一个非空字符串 $s$，由小写英文字母组成，其长度至多为 1500 个字符。

输入的第二行是一个仅由字符 "0" 和 "1" 组成的字符串，长度恰好为 26。若该字符串的第 $i$ 个字符为 "1"，则第 $i$ 个英文字母是“好”的；否则为“坏”的。即：该字符串的第一个字符对应字母 "a"，第二个字符对应字母 "b"，依此类推。

输入的第三行包含一个整数 $k$（$0 \le k \le |s|$），表示一个“好子串”中最多允许出现的“坏字符”个数。

Print a single integer — the number of distinct good substrings of string s.

输出一个整数——字符串 $s$ 中不同“好子串”的数量。

In the first example there are following good substrings: "a", "ab", "b", "ba", "bab".

In the second example there are following good substrings: "a", "aa", "ac", "b", "ba", "c", "ca", "cb".

在第一个例子中，以下子串是“好”的：“a”、“ab”、“b”、“ba”、“bab”。

在第二个例子中，以下子串是“好”的：“a”、“aa”、“ac”、“b”、“ba”、“c”、“ca”、“cb”。