你有字符串 s,由小英文字母组成。有些英文字母很好,其余的很糟糕。
字符串 s = s1s2...s|s| 的子串 s[l...r] (1 ≤ l ≤ r ≤ |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 的不同好子串的数量。
示例
输入 #1
ababab 01000000000000000000000000 1
输出 #1
5
输入 #2
acbacbacaa 00000000000000000000000000 2
输出 #2
8
注意
在第一个示例中,有以下好的子字符串:“a”、“ab”、“b”、“ba”、“bab”。
在第二个示例中,有以下好的子字符串:“a”、“aa”、“ac”、“b”、“ba”、“c”、“ca”、“cb”。