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 = s1s2...s|s| (where |s| is the length of string s) is string  slsl + 1...sr.

The substring s[l...r] is good, if among the letters  sl, sl + 1, ..., sr 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".
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class _271D {

//    Java implementation
//    1. lcp(x, y)表示是的s[x..], s[y..]的lcp
//    2. index[x]表示的是rank是x的suffix的index
//    比如如果需要求rank是0的和rank是1的两个suffix的lcp，就应该写成
//    sa.lcp(sa.index[0], sa.index[1])

    static class SuffixArray {
        private char str[];
        private int MAX_LOG = 30;
        private int n, nr0[], nr1[], rank[][], index[], step, cnt;

        private int M;
        private int minusOneHead;
        private int minusOneTail;
        private int bucketHead[];
        private int bucketTail[];
        private int pointTo[];
        private int next[];
        private int globalPtr;

        public SuffixArray(String s) {
            str = s.toCharArray();
            n = str.length;
            nr0 = new int[n];
            nr1 = new int[n];
            index = new int[n];
            rank = new int[MAX_LOG][n];
            M = Math.max(128, n);
            bucketHead = new int[M];
            bucketTail = new int[M];
            pointTo = new int[M];
            next = new int[M];

            for (int i = 0; i < n; i++)
                rank[0][i] = str[i];

            boolean needSort = true;
            for (step = cnt = 1; (cnt >> 1) < n; step++, cnt <<= 1) {
                if (!needSort) {
                    for (int i = 0; i < n; i++)
                        rank[step][i] = rank[step - 1][i];
                    continue;
                }
                for (int i = 0; i < n; i++) {
                    nr0[i] = rank[step - 1][i];
                    nr1[i] = i + cnt < n ? rank[step - 1][i + cnt] : -1;
                    index[i] = i;
                }

                radixSort1();
                radixSort0();

                needSort = false;
                for (int i = 0; i < n; i++) {
                    if (i > 0 && nr0[index[i]] == nr0[index[i - 1]] && nr1[index[i]] == nr1[index[i - 1]]) {
                        rank[step][index[i]] = rank[step][index[i - 1]];
                        needSort = true;
                    } else rank[step][index[i]] = i;
                }
            }
        }

        private void radixSort0() {
            globalPtr = 0;
            Arrays.fill(bucketHead, -1);
            Arrays.fill(next, -1);

            for (int i = 0; i < n; i++) {
                int value = nr0[index[i]];
                if (bucketHead[value] == -1) bucketHead[value] = bucketTail[value] = globalPtr;
                else bucketTail[value] = next[bucketTail[value]] = globalPtr;
                pointTo[globalPtr++] = index[i];
            }

            int ptr = 0;
            for (int i = 0; i < M; i++)
                for (int j = bucketHead[i]; j != -1; j = next[j])
                    index[ptr++] = pointTo[j];
        }

        private void radixSort1() {
            globalPtr = 0;
            Arrays.fill(bucketHead, -1);
            Arrays.fill(next, -1);
            minusOneHead = minusOneTail = -1;

            for (int i = 0; i < n; i++) {
                int value = nr1[index[i]];
                if (value == -1) {
                    if (minusOneHead == -1) minusOneHead = minusOneTail = globalPtr;
                    else minusOneTail = next[minusOneTail] = globalPtr;
                } else {
                    if (bucketHead[value] == -1) bucketHead[value] = bucketTail[value] = globalPtr;
                    else bucketTail[value] = next[bucketTail[value]] = globalPtr;
                }
                pointTo[globalPtr++] = index[i];
            }

            int ptr = 0;
            for (int j = minusOneHead; j != -1; j = next[j])
                index[ptr++] = pointTo[j];
            for (int i = 0; i < M; i++)
                for (int j = bucketHead[i]; j != -1; j = next[j])
                    index[ptr++] = pointTo[j];
        }

        public int lcp(int x, int y) {
            int k, ret = 0;
            if (x == y) return n - x;
            for (k = step - 1; k >= 0 && x < n && y < n; k--)
                if (rank[k][x] == rank[k][y]) {
                    x += 1 << k;
                    y += 1 << k;
                    ret += 1 << k;
                }
            return ret;
        }
    }

    public static void main(String[] args) throws Exception {
        Reader.init(System.in);
        BufferedWriter cout = new BufferedWriter(new OutputStreamWriter(System.out));

        String s = Reader.next();
        char[] mask = Reader.next().toCharArray();
        int k = Reader.nextInt();

        SuffixArray sa = new SuffixArray(s);
        int ans = 0;
        for (int i = 0; i < s.length() - 1; i++) {
//            System.out.println(sa.index[i] + " " + sa.index[i + 1] + " " + sa.lcp(sa.index[i], sa.index[i + 1]));
            int lcp = sa.lcp(sa.index[i], sa.index[i + 1]);
            int cnt = 0;
            for (int j = sa.index[i]; j < s.length(); j++) {
                if (mask[s.charAt(j) - 'a'] == '0') {
                    if (++cnt > k) break;
                }
                if (j >= sa.index[i] + lcp) ans++;
            }
//            System.out.println(ans);
        }
        int cnt = 0;
        for (int i = sa.index[s.length() - 1]; i < s.length(); i++) {
            if (mask[s.charAt(i) - 'a'] == '0') {
                if (++cnt > k) break;
            }
            ans++;
        }

        System.out.println(ans);
        cout.close();
    }

    static class Pair<U extends Comparable<U>, V extends Comparable<V>> implements Comparable<Pair<U, V>> {
        final U _1;
        final V _2;

        private Pair(U key, V val) {
            this._1 = key;
            this._2 = val;
        }

        public static <U extends Comparable<U>, V extends Comparable<V>> Pair<U, V> instanceOf(U _1, V _2) {
            return new Pair<U, V>(_1, _2);
        }

        @Override
        public String toString() {
            return _1 + " " + _2;
        }

        @Override
        public int hashCode() {
            int res = 17;
            res = res * 31 + _1.hashCode();
            res = res * 31 + _2.hashCode();
            return res;
        }

        @Override
        public int compareTo(Pair<U, V> that) {
            int res = this._1.compareTo(that._1);
            if (res < 0 || res > 0) return res;
            else return this._2.compareTo(that._2);
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (!(obj instanceof Pair)) return false;
            Pair<?, ?> that = (Pair<?, ?>) obj;
            return _1.equals(that._1) && _2.equals(that._2);
        }
    }

    /**
     * Class for buffered reading int and double values
     */
    static class Reader {
        static BufferedReader reader;
        static StringTokenizer tokenizer;

        /**
         * call this method to initialize reader for InputStream
         */
        static void init(InputStream input) {
            reader = new BufferedReader(new InputStreamReader(input));
            tokenizer = new StringTokenizer("");
        }

        /**
         * get next word
         */
        static String next() throws IOException {
            while (!tokenizer.hasMoreTokens()) {
                // TODO add check for eof if necessary
                tokenizer = new StringTokenizer(reader.readLine());
            }
            return tokenizer.nextToken();
        }

        static int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        static double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
    }

    static class ArrayUtil {
        static void swap(int[] a, int i, int j) {
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }

        static void swap(long[] a, int i, int j) {
            long tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }

        static void swap(double[] a, int i, int j) {
            double tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }

        static void swap(char[] a, int i, int j) {
            char tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }

        static void swap(boolean[] a, int i, int j) {
            boolean tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }

        static void reverse(int[] a, int i, int j) {
            for (; i < j; i++, j--)
                swap(a, i, j);
        }

        static void reverse(long[] a, int i, int j) {
            for (; i < j; i++, j--)
                swap(a, i, j);
        }

        static void reverse(double[] a, int i, int j) {
            for (; i < j; i++, j--)
                swap(a, i, j);
        }

        static void reverse(char[] a, int i, int j) {
            for (; i < j; i++, j--)
                swap(a, i, j);
        }

        static void reverse(boolean[] a, int i, int j) {
            for (; i < j; i++, j--)
                swap(a, i, j);
        }

        static long sum(int[] a) {
            int sum = 0;
            for (int i : a)
                sum += i;
            return sum;
        }

        static long sum(long[] a) {
            long sum = 0;
            for (long i : a)
                sum += i;
            return sum;
        }

        static double sum(double[] a) {
            double sum = 0;
            for (double i : a)
                sum += i;
            return sum;
        }

        static int max(int[] a) {
            int max = Integer.MIN_VALUE;
            for (int i : a)
                if (i > max) max = i;
            return max;
        }

        static int min(int[] a) {
            int min = Integer.MAX_VALUE;
            for (int i : a)
                if (i < min) min = i;
            return min;
        }

        static long max(long[] a) {
            long max = Long.MIN_VALUE;
            for (long i : a)
                if (i > max) max = i;
            return max;
        }

        static long min(long[] a) {
            long min = Long.MAX_VALUE;
            for (long i : a)
                if (i < min) min = i;
            return min;
        }
    }
}
