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_1s_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].


-----Input-----

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.


-----Output-----

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


-----Examples-----
Input
ababab
01000000000000000000000000
1

Output
5

Input
acbacbacaa
00000000000000000000000000
2

Output
8



-----Note-----

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".

Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures
Skill types: Data structures

Starter code:

Solutions:
s = input()
a = input()
k = int(input())
S = sorted((s[i:] for i in range(len(s))))
p = ''
r = 0
for e in S:
	t = 0
	s = 0
	for i in range(len(e)):
		if i >= len(p) or e[i] != p[i]:
			s = 1
		if a[ord(e[i]) - ord('a')] == '0':
			t += 1
		if t > k:
			break
		if s:
			r += 1
	p = e
print(r)


import os
import sys
from io import BytesIO, IOBase
alph = dict()
for i in range(26):
	alph[chr(i + 97)] = i

def main():
	txt = input()
	n = len(txt)
	arr = list(map(int, input()))
	k = int(input())
	suffixArr = [txt[i:] for i in range(n)]
	suffixArr.sort()
	prev = ''
	ans = 0
	for s in suffixArr:
		count = 0
		flag = 0
		for j in range(len(s)):
			if j >= len(prev) or s[j] != prev[j]:
				flag = 1
			count += 1 - arr[alph[s[j]]]
			if count > k:
				break
			if flag:
				ans += 1
		prev = s
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')
main()


s = input()
L = input()
k = int(input())
good = set()
string = set()
LIST = [chr(i) for i in range(97, 123)]
for i in range(26):
	if L[i] == '1':
		good.add(LIST[i])
t = [s[i] not in good for i in range(len(s))]
end = [0] * len(s)
badchars = 0
front = 0
rear = 0
while front < len(s):
	while rear < len(s):
		badchars += t[rear]
		if badchars > k:
			badchars -= 1
			break
		rear += 1
	end[front] = rear
	badchars -= t[front]
	front += 1
for i in range(len(s)):
	tempStrHash = 0
	for j in range(i, end[i]):
		tempStrHash = tempStrHash * 29 + ord(s[j]) - 96 & 1152921504606846975
		string.add(tempStrHash)
print(len(string))


import collections
import time
import os
import sys
import bisect
import heapq
from typing import List

def solve(S, B, K):
	MOD = (1 << 50) + 9
	s = set()
	N = len(S)
	pow = [1 for _ in range(N + 1)]
	for i in range(1, N + 1):
		pow[i] = pow[i - 1] * 26
		pow[i] %= MOD
	for i in range(N - 1, -1, -1):
		(k, h) = (0, 0)
		for j in range(i, -1, -1):
			ch = S[j]
			if B[ch]:
				k += 1
			if k > K:
				break
			h += (ord(ch) - ord('a') + 1) * pow[i - j]
			h %= MOD
			s.add(h)
	return len(s)
S = input()
B = list(input())
K = int(input())
B = {chr(ord('a') + i): False if B[i] == '1' else True for i in range(26)}
print(solve(S, B, K))


p = 31
q = 1000000007
p0 = 27
q0 = 2147483647

class hstr:

	def __init__(self, s):
		self.h = [0]
		self.pq = [1]
		self.h0 = [0]
		self.pq0 = [1]
		n = len(s)
		for i in range(n):
			self.h += [(self.h[i] * p + ord(s[i])) % q]
			self.pq += [self.pq[i] * p % q]
			self.h0 += [(self.h0[i] * p0 + ord(s[i])) % q0]
			self.pq0 += [self.pq0[i] * p0 % q0]

	def get(self, l, r):
		return ((self.h[r] - self.h[l] * self.pq[r - l]) % q + q) % q

	def get0(self, l, r):
		return ((self.h0[r] - self.h0[l] * self.pq0[r - l]) % q0 + q0) % q0
from sys import stdout
from sys import stdin

def get():
	return stdin.readline().strip()

def getf():
	return [int(i) for i in get().split()]

def put(a, end='\n'):
	stdout.write(str(a) + end)

def putf(a, sep=' ', end='\n'):
	stdout.write(sep.join([str(i) for i in a]) + end)

def main():
	s = get()
	a = get()
	h = hstr(s)
	k = int(get())
	r = []
	for i in a:
		if i == '1':
			r += [0]
		else:
			r += [1]
	ns = [0]
	for i in s:
		ns += [r[ord(i) - 97] + ns[-1]]
	st = set()
	ans = 0
	n = len(s)
	for i in range(n):
		for j in range(i + 1, n + 1):
			res = h.get(i, j) * h.get0(i, j)
			if res not in st:
				st.add(res)
				if ns[j] - ns[i] <= k:
					ans += 1
	put(ans)
main()


import sys
import math as mt
t = 1
mod = 9007199254740881
for ___ in range(t):
	s1 = input()
	s2 = input()
	k = int(input())
	d = {}
	for i in range(len(s1)):
		suma = 0
		pre = 0
		D = 256
		for j in range(i, len(s1)):
			pre = (pre * D + ord(s1[j])) % mod
			posi = ord(s1[j]) - ord('a')
			if s2[posi] == '0':
				suma += 1
			if suma <= k:
				d[pre] = 1
			else:
				break
	print(len(d))


import random
import math
import heapq
import collections
from collections import defaultdict
from collections import Counter
from collections import OrderedDict
from typing import List
from collections import deque
from functools import lru_cache
from bisect import bisect_left
import bisect
from itertools import product

def trace(*args, **kwargs):
	print(*args, file=sys.stderr, **kwargs)
import sys, os.path
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')

def input():
	return sys.stdin.readline().rstrip()

def ini():
	return int(input())

def inl():
	return list(map(int, input().split()))

def ins():
	return input()
s = ins()
d = [1 - int(x) for x in ins()]
limit = ini()
n = len(s)
trie = [[-1 for _ in range(26)]]
tot = 0
for i in range(n):
	cnt = 0
	p = 0
	for j in range(i, n):
		c = ord(s[j]) - ord('a')
		cnt += d[c]
		if cnt > limit:
			break
		if trie[p][c] == -1:
			trie.append([-1] * 26)
			tot += 1
			trie[p][c] = tot
		p = trie[p][c]
print(tot)


def index(c):
	return ord(c) - ord('a')

class Trie:

	def __init__(self):
		self._children = {}
		self.mark = False

	def get(self, c):
		i = index(c)
		if i not in self._children:
			self._children[i] = Trie()
		return self._children[i]

def solve(s, k, is_good):
	n = len(s)
	trie = Trie()
	res = 0
	for i in range(n):
		bad = 0
		cur = trie
		for j in range(i, n):
			if not is_good[index(s[j])]:
				bad += 1
				if bad > k:
					break
			cur = cur.get(s[j])
			if not cur.mark:
				res += 1
				cur.mark = True
	return res
s = input()
is_good = [c == '1' for c in input()]
k = int(input())
print(solve(s, k, is_good))


import collections as cc
import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
S = lambda : list(input().strip())
s = S()
t = S()
(k,) = I()
ans = 0
prev = ''
ss = sorted([s[i:] for i in range(len(s))])
for j in ss:
	now = 0
	f = 0
	for i in range(len(j)):
		if i >= len(prev) or j[i] != prev[i]:
			f = 1
		now += t[ord(j[i]) - ord('a')] == '0'
		if now > k:
			break
		if f:
			ans += 1
	prev = j
print(ans)


s = input()
l = input()
k = int(input())
no_bad = []
curr = 0
p = 31
m = 67280421310721
hashes = []
currh = 0
cnt = 0
P = [pow(p, i, m) for i in range(len(s) + 2)]
for i in s:
	currh += P[cnt] * ord(i) % m
	cnt += 1
	hashes.append(currh)
	if l[ord(i) - ord('a')] == '0':
		no_bad.append(curr + 1)
		curr += 1
	else:
		no_bad.append(curr)
no_bad.append(0)
hashes.append(0)
ans = set()
for i in range(len(s)):
	for j in range(i, len(s)):
		if no_bad[j] - no_bad[i - 1] <= k:
			has = (hashes[j] - hashes[i - 1]) * P[len(s) - i + 1] % m
			ans.add(has)
print(len(ans))


s = input()
L = input()
k = int(input())
l = len(s)
good = set()
string = set()
LIST = [chr(i) for i in range(97, 123)]
for i in range(26):
	if L[i] == '1':
		good.add(LIST[i])
t = [s[i] not in good for i in range(l)]
end = [0] * l
sumbad = 0
(i, j) = (0, 0)
while i < l:
	if j < l:
		sumbad += t[j]
	if sumbad > k or j == l:
		sumbad -= t[i]
		end[i] = j
		i += 1
		if sumbad > k:
			sumbad -= t[j]
			continue
	if j < l:
		j += 1
for i in range(len(s)):
	t = 0
	for j in range(i, end[i]):
		t = t * 29 + ord(s[j]) - 96 & 1152921504606846975
		string.add(t)
print(len(string))


import sys
input = sys.stdin.readline
s = input().rstrip()
flag = input().rstrip()
k = int(input())
n = len(s)
ss = [s[i:] for i in range(n)]
ss.sort()
pre = ''
ans = 0
for e in ss:
	(veri, cnt_bad) = (0, 0)
	for i in range(len(e)):
		if i >= len(pre) or e[i] != pre[i]:
			veri = 1
		cnt_bad += flag[ord(e[i]) - ord('a')] == '0'
		if cnt_bad > k:
			break
		if veri:
			ans += 1
	pre = e
print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
s = input()
l = [int(k) for k in input()]
bad = set()
for i in range(26):
	if l[i] == 0:
		bad.add(97 + i)
k = int(input())
hashes = set()
base = 999983
s = [ord(x) for x in s]
value = 0
badcount = 0
mod = 10 ** 16 + 11
basemod = [1] * 1501
for i in range(1, 1501):
	basemod[i] = basemod[i - 1] * base % mod
for length in range(1, len(s) + 1):
	value = value * base % mod
	value = (value + s[length - 1]) % mod
	if s[length - 1] in bad:
		badcount += 1
	if badcount <= k:
		hashes.add(value)
	(val, brbad) = (value, badcount)
	for i in range(length, len(s)):
		if s[i] in bad:
			brbad += 1
		if s[i - length] in bad:
			brbad -= 1
		val = ((val - s[i - length] * basemod[length - 1]) * base + s[i]) % mod
		if brbad <= k:
			hashes.add(val)
print(len(hashes))


s = input()
a = input()
k = int(input())
d = sorted((s[i:] for i in range(len(s))))
c = ''
r = 0
for j in d:
	pos = 0
	s = 0
	for i in range(len(j)):
		if i >= len(c) or j[i] != c[i]:
			s = 1
		if a[ord(j[i]) - ord('a')] == '0':
			pos += 1
		if pos > k:
			break
		if s:
			r += 1
	c = j
print(r)


s = input()
good = [int(x) for x in input()]
k = int(input())
n = len(s)
ans = 0
mod = 10 ** 15 + 9
dp = [[0 for _ in range(n)] for _ in range(n)]
hashes = [ord(s[0]) - ord('a') + 1]
if good[ord(s[0]) - ord('a')]:
	dp[0][0] = 0
else:
	dp[0][0] = 1
for i in range(1, n):
	hashes.append(hashes[-1] + (ord(s[i]) - ord('a') + 1) * 29 ** i)
for i in range(n):
	hashes[i] = hashes[i] % mod
occ = set()
ppowi = []
for i in range(n + 1):
	ppowi.append(29 ** i % mod)
for i in range(n):
	for j in range(i, n):
		if i - 1 >= 0:
			x = (hashes[j] - hashes[i - 1]) * ppowi[n - i] % mod
		else:
			x = hashes[j] * ppowi[n] % mod
		if i == 0 and j == 0:
			dp[i][j] = 1 ^ good[ord(s[j]) - ord('a')]
		elif good[ord(s[j]) - ord('a')] == 0:
			dp[i][j] = dp[i][j - 1] + 1
		else:
			dp[i][j] = dp[i][j - 1]
		if dp[i][j] > k:
			break
		if dp[i][j] <= k:
			occ.add(x)
print(len(occ))


s = input()
alpha = input()
k = int(input())
subs = sorted((s[i:] for i in range(len(s))))
prev = ''
ans = 0
for j in subs:
	uni = False
	bad = 0
	for i in range(len(j)):
		if i >= len(prev) or prev[i] != j[i]:
			uni = True
		if alpha[ord(j[i]) - ord('a')] == '0':
			bad += 1
		if bad > k:
			break
		if uni:
			ans += 1
	prev = j
print(ans)