#include <bits/stdc++.h>
using namespace std;
const long long N = 1500 + 5, K = 501;
string bad;
long long k;
typedef struct data {
  data* bit[27];
  long long cnt = 0;
} trie;
trie* head;
void insert(string s) {
  trie* node = head;
  for (long long i = 0; i < s.size(); i++) {
    char c = s[i];
    if (node->bit[c - 'a'] == NULL) {
      node->bit[c - 'a'] = new trie();
      node->bit[c - 'a']->cnt = node->cnt;
      if (bad[c] == '0') node->bit[c - 'a']->cnt++;
    }
    node = node->bit[c - 'a'];
  }
}
long long query(trie* node, long long cnt) {
  long long ans = 0;
  for (long long i = 0; i < 26; i++) {
    if (node->bit[i] != NULL) {
      if (bad[i] == '1')
        ans += 1 + query(node->bit[i], cnt);
      else if (cnt)
        ans += 1 + query(node->bit[i], cnt - 1);
    }
  }
  return ans;
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long long TESTS = 1;
  while (TESTS--) {
    head = new trie();
    string s;
    cin >> s;
    cin >> bad >> k;
    long long n = s.size();
    string sub;
    for (long long i = n - 1; i >= 0; i--) {
      sub = s[i] + sub;
      insert(sub);
    }
    long long ans = query(head, k);
    cout << ans << endl;
  }
  return 0;
}
