Hash for a string

// I can't tell you what it really is,
// I can only tell you what it feels like.
#include "bits/stdc++.h"
using namespace std;

const int MOD = (1L<<31)-1;


int rand(int l, int r){
    static std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
    std::uniform_int_distribution<int> ludo(l, r); return ludo(rng);
}

struct mod_int {
    int val;
    mod_int(long long v = 0) {
        if (v < 0) v = v % MOD + MOD;
        if (v >= MOD) v %= MOD;
        val = v;
    }

    static int mod_inv(int a, int m = MOD) {
        int g = m, r = a, x = 0, y = 1;
        while (r != 0) {
            int q = g / r;
            g %= r; swap(g, r);
            x -= q * y; swap(x, y);
        }
        return x < 0 ? x + m : x;
    }

    mod_int& operator+=(const mod_int &other) {
        val += other.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }

    mod_int& operator-=(const mod_int &other) {
        val -= other.val;
        if (val < 0) val += MOD;
        return *this;
    }

    static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
      return x % m;
    }

    mod_int& operator*=(const mod_int &other) {
        val = fast_mod((uint64_t) val * other.val);
        return *this;
    }

    mod_int& operator/=(const mod_int &other) {
        return *this *= other.inv();
    }

    friend mod_int operator+(const mod_int &a, const mod_int &b) { return mod_int(a) += b; }
    friend mod_int operator-(const mod_int &a, const mod_int &b) { return mod_int(a) -= b; }
    friend mod_int operator*(const mod_int &a, const mod_int &b) { return mod_int(a) *= b; }
    friend mod_int operator/(const mod_int &a, const mod_int &b) { return mod_int(a) /= b; }

    mod_int& operator++() {
        val = val == MOD - 1 ? 0 : val + 1;
        return *this;
    }

    mod_int& operator--() {
        val = val == 0 ? MOD - 1 : val - 1;
        return *this;
    }

    mod_int operator++(int) { mod_int before = *this; ++*this; return before; }
    mod_int operator--(int) { mod_int before = *this; --*this; return before; }

    mod_int operator-() const {
        return val == 0 ? 0 : MOD - val;
    }

    bool operator==(const mod_int &other) const { return val == other.val; }
    bool operator!=(const mod_int &other) const { return val != other.val; }

    mod_int inv() const {
        return mod_inv(val);
    }

    mod_int pow(long long p) const {
        assert(p >= 0);
        mod_int a = *this, result = 1;

        while (p > 0) {
            if (p & 1)
                result *= a;

            a *= a;
            p >>= 1;
        }

        return result;
    }

    friend ostream& operator<<(ostream &stream, const mod_int &m) {
        return stream << m.val;
    }
};

const int N = 1505;
char s[N], bad[30];
int k;

struct Hash {
	vector<mod_int> H, pre;
	Hash(char *s, int N) {
		H.resize(N+1);
		pre.resize(N+1);
		mod_int base = rand(35, 1<<10);
		// cout << base << '\n';
		pre[0] = 1;
		mod_int cur = 0;
		for (int i = 1; i <= N; ++i) {
			pre[i] = pre[i-1] * base;
			cur = cur * base + (s[i] - 'a' + 1);
			H[i] = cur;
			// cout << cur << ' ';
		}
		// cout << endl;
	}
	unsigned get_hash(int l, int r) {
		mod_int rem = pre[r-l+1] * H[l-1];
		return mod_int(H[r] - rem).val;
	}

};

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> s+1 >> bad >> k;
  int N = strlen(s+1);
  Hash ins1(s, N), ins2(s, N);
  // cout << endl;
  for (int i = 1; i <= N; i += 2) {
  	// cout << ins1.get_hash(i,i+1) << ' ' << ins2.get_hash(i,i+1) << '\n';
  }
  set<pair<unsigned,unsigned>> st;
  // set<unsigned> st1, st2;
	for (int i = 1; i <= N; ++i) {
    int badTillNow = 0;
    for (int j = i; j <= N; ++j) {
      badTillNow += bad[s[j]-'a'] == '0';
      if (badTillNow > k) {
        break;
      }
      st.insert(make_pair(ins1.get_hash(i, j), ins2.get_hash(i,j)));
      // st1.insert(ins1.get_hash(i,j));
      // st2.insert(ins2.get_hash(i,j));
    }
  }
  cout << st.size() << '\n';//min(st1.size(), st2.size());
  return 0;
}
// 1). Try forming/rearranging the equations if any
// 2). If problem asks to count, try counting in reverse(it can be easier sometimes)