#include <bits/stdc++.h>
using namespace std;
const int oo = 0x3f3f3f3f;
const double eps = 1e-9;
char good[100];
int K;
int S = 1;
char buf[1024 * 1000];
const int MAXN = 2 * 1000 * 1008;
char *Str[1];
vector<int> labels[MAXN];
int N, Cur, Ch[MAXN], Sib[MAXN], Par[MAXN], Suf[MAXN], Num[MAXN], P1[MAXN],
    P2[MAXN];
void init(int n, int ch, int sib, int par, int suf, int num, int p1, int p2) {
  Ch[n] = ch, Sib[n] = sib, Par[n] = par, Suf[n] = suf, Num[n] = num,
  P1[n] = p1, P2[n] = p2;
  labels[n].clear();
}
int scan(pair<int, int> &p, char *s) {
  for (int i = 0;; i++, p.second++) {
    if (p.second == P2[p.first]) {
      for (int j = Ch[p.first]; j != -1; j = Sib[j]) {
        if (Str[Num[j]][P1[j]] == s[i]) {
          p = pair<int, int>(j, P1[j]);
          break;
        }
      }
    }
    if (p.second == P2[p.first] || Str[Num[p.first]][p.second] != s[i])
      return i;
  }
}
void scan2(pair<int, int> &p, int a, int b) {
  while (a < b) {
    for (p.first = Ch[p.first]; Str[Num[p.first]][P1[p.first]] != Str[Cur][a];
         p.first = Sib[p.first])
      ;
    a += P2[p.first] - P1[p.first];
  }
  p.second = P2[p.first] - a + b;
}
void insert(int n, pair<int, int> &p) {
  if (p.second < P2[p.first]) {
    if (Ch[Par[p.first]] == p.first) {
      Ch[Par[p.first]] = N;
    } else {
      int t = Ch[Par[p.first]];
      while (Sib[t] != p.first) t = Sib[t];
      Sib[t] = N;
    }
    init(N++, p.first, Sib[p.first], Par[p.first], -1, Num[p.first],
         P1[p.first], p.second);
    Sib[p.first] = -1, Par[p.first] = N - 1, P1[p.first] = p.second;
    p = pair<int, int>(N - 1, P2[N - 1]);
  }
  Sib[n] = Ch[p.first], Par[n] = p.first, Ch[p.first] = n;
}
void buildGST() {
  N = 1;
  init(0, -1, -1, 0, 0, 0, 0, 0);
  for (Cur = 0; Cur < S; Cur++) {
    int len = strlen(Str[Cur]), sc = 0, sc2 = 0, last = 0;
    pair<int, int> p(0, 0);
    for (int i = (0); i < (len + 1); i++) {
      if (sc < i) sc = i;
      if (sc2 < i) sc2 = i;
      scan2(p, sc2, sc);
      if (p.second == P2[p.first]) {
        if (Suf[last] == -1) Suf[last] = p.first;
        sc += scan(p, Str[Cur] + sc);
      }
      if (p.first && p.second == P2[p.first] && Ch[p.first] == -1) {
        labels[p.first].push_back(Cur);
      } else {
        init(N++, -1, -1, -1, -1, Cur, sc, len + 1);
        labels[N - 1].push_back(Cur);
        insert(N - 1, p);
        if (Suf[last] == -1) Suf[last] = p.first;
        last = p.first;
      }
      sc2 = sc;
      if (Suf[p.first] == -1) {
        sc2 -= (P2[p.first] - P1[p.first]);
        p.first = Par[p.first];
      }
      p = pair<int, int>(Suf[p.first], P2[Suf[p.first]]);
    }
  }
}
int rek(int u, int m) {
  int p = P1[u];
  int res = 0;
  for (int i = 0;; i++, p++) {
    if (p == P2[u]) {
      for (int j = Ch[u]; j != -1; j = Sib[j]) {
        res += rek(j, m);
      }
      return res;
    }
    if (!Str[Num[u]][p]) return res;
    if (good[(int)(Str[Num[u]][p] - 'a')] == '0') m++;
    if (m > K) return res;
    res++;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  scanf("%s%s%d", buf, good, &K);
  Str[0] = buf;
  buildGST();
  cout << rek(0, 0) << endl;
}
