Number of good substrings

Interview

Time limit2sMemory limit512 MB

Summary

Count how many distinct substrings of s contain at most k bad letters, counting equal substrings once.

Level: Medium6 of 10
Topics: String, Hash map, Sliding window
Solved: No attempts yet

Problem

You are given a string $s$ made of lowercase English letters. Each of the 26 letters is either good or bad.

For a string $s = s_1 s_2 \dots s_{|s|}$ of length $|s|$ , the substring $s[l \dots r]$ ( $1 \le l \le r \le |s|$ ) is $s_l s_{l+1} \dots s_r$ .

A substring $s[l \dots r]$ is good if at most $k$ of the letters $s_l, s_{l+1}, \dots, s_r$ are bad.

Write a program that counts the distinct good substrings of $s$ . Two substrings $s[x \dots y]$ and $s[p \dots q]$ count as different when $s[x \dots y] \ne s[p \dots q]$ . Substrings with the same content at different positions are counted once.

Input

The first line contains a string $s$ of lowercase English letters. The length of $s$ is at most 1500.

The second line contains a string of length 26 made of 0 and 1. If the $i$ -th character is 1, the $i$ -th letter is good, and if it is 0, that letter is bad. The first character stands for the letter 'a', and the second one stands for 'b'.

The third line contains $k$ ( $0 \le k \le |s|$ ).

Output

Print the number of distinct good substrings of $s$ .

Examples5

Example 1
Input
```
ababab
01000000000000000000000000
1
```
Expected output
```
5
```

Example 2

Input

acbacbacaa
00000000000000000000000000
2

Expected output

Example 3
Input
```
a
10000000000000000000000000
0
```
Expected output
```
1
```
Example 4
Input
```
a
00000000000000000000000000
0
```
Expected output
```
0
```

Example 5

Input

aaaaaaaaaa
11111111111111111111111111
0

Expected output