D. Хорошие подстрочки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
stdin
вывод
stdout

Вам дана строка s, состоящая из строчных латинских букв. Некоторые из латинских букв являются хорошими, остальные — плохими.

Подстрокой s[l...r] (1 ≤ l ≤ r ≤ |s|) строки s  =  s1s2...s|s| (где |s| — длина строки s) называется строка  slsl + 1...sr.

Подстроку s[l...r] назовем хорошей, если среди букв  sl, sl + 1, ..., sr не более k являются плохими (смотрите пояснения к примерам для лучшего понимания).

Ваша задача — найти количество различных хороших подстрок данной строки s. Две подстроки s[x...y] и s[p...q] различны, если различно их содержимое, то есть s[x...y] ≠ s[p...q].

Входные данные

Первая строка входных данных — это непустая строка s, состоящая из строчных латинских букв, длиной не более 1500 символов.

Вторая строка входных данных — это строка из символов «0» и «1» длиной ровно 26 символов. Если i-ый символ этой строки равен «1», то i-ая буква латинского алфавита является хорошей, иначе — плохой. То есть первый символ этой строки соответствует букве «a», второй — букве «b» и так далее.

В третьей строке входных данных записано единственное целое число k (0 ≤ k ≤ |s|) — максимальное допустимое количество плохих символов в хорошей подстроке.

Выходные данные

Выведите единственное целое число — количество различных хороших подстрок строки s.

Примеры
Входные данные
ababab
01000000000000000000000000
1
Выходные данные
5
Входные данные
acbacbacaa
00000000000000000000000000
2
Выходные данные
8
Примечание

В первом примере хорошими подстроками являются: «a», «ab», «b», «ba», «bab».

Во втором примере хорошими подстроками являются: «a», «aa», «ac», «b», «ba», «c», «ca», «cb».