좋은 부분 문자열의 개수

알파벳 소문자로만 이루어진 문자열 $s$가 주어진다. 26개의 알파벳은 각각 좋은 알파벳이거나 나쁜 알파벳이다.

길이가 $|s|$인 문자열 $s = s_1 s_2 \dots 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] \ne s[p \dots q]$인 경우에 두 부분 문자열 $s[x \dots y]$와 $s[p \dots q]$를 서로 다르다고 한다. 위치가 달라도 내용이 같은 부분 문자열은 한 번만 센다.

첫째 줄에 알파벳 소문자로 이루어진 문자열 $s$가 주어진다. $s$의 길이는 1500을 넘지 않는다.

둘째 줄에 0과 1로 이루어진 길이 26의 문자열이 주어진다. $i$번째 글자가 1이면 $i$번째 알파벳이 좋은 알파벳이고, 0이면 나쁜 알파벳이다. 첫 번째 문자는 알파벳 'a'를 나타내고, 두 번째 문자는 'b'를 나타낸다.

셋째 줄에 $k$가 주어진다. ($0 \le k \le |s|$)

$s$의 서로 다른 좋은 부분 문자열의 개수를 출력한다.