알파벳 소문자로 이루어진 문자열 s가 주어진다. 알파벳 중에서 일부는 좋고, 나머지는 나쁘다.</p>

문자열 s = s₁s₂...s_|s|(|s|는 문자열 s의 길이)의 부분 문자열 s[l...r] (1 ≤ l ≤ r ≤ |s|)는 s_ls_l+1...s_r 이다.

만약, s[l...r]을 이루고 있는 알파벳 s_l, s_l+1, ..., s_r 중에서 나쁜 알파벳의 개수가 최대 k개라면, 그 부분 문자열을 좋다고 한다.

s의 서로 다른 좋은 부분 문자열의 개수를 찾는 프로그램을 작성하시오. s[x...y] ≠ s[p...q]인 경우에 두 부분 문자열 s[x...y]와 s[p...q]를 서로 다르다고 한다.

입력 형식

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

둘째 줄에는 26개의 0과 1로 이루어진 문자열이 주어진다. i번째 글자가 1인 경우에는 i번째 알파벳이 좋은 알파벳이라는 것, 0인 경우는 나쁜 알파벳이라는 것을 의미한다. 즉, 첫 번째 문자는 알파벳 'a'를 나타내며, 두 번째 문자는 'b'를 나타낸다.

셋째 줄에는 k (0 ≤ k ≤ |s|)가 주어진다.

출력 형식

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

예제 입력 1

ababab
01000000000000000000000000
1

예제 출력 1

5

예제 입력 2

acbacbacaa
00000000000000000000000000
2

예제 출력 2

8