#include <bits/stdc++.h>

using namespace std;

#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define          file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

// end of template

const int MAX_LR = 202;
const int MAX_X = 22;
const int MAX_K = 1e4 + 4;
const int MOD = 1e9 + 7;

string L, R, X;
int K, v[MAX_X], kmp[MAX_X], nxt[MAX_X][10];

void init(void) {
	cin >> L >> R >> X >> K;
	REP(i, X.size()) cin >> v[i + 1];
}

void add(int &a, int b) {
	a += b;
	if (a >= MOD) a -= MOD;
}

int dp[MAX_LR][MAX_X][MAX_K][2];

int solve(const string &R) {
	memset(dp, 0, sizeof(dp));
	dp[0][0][0][0] = 1;
	REP(i, R.size()) REP(suff, X.size() + 1) REP(beauty, K + 1) REP(less_r, 2) if (dp[i][suff][beauty][less_r]) {
		REP(digit, less_r ? 10 : R[i] - '0' + 1) {
			int new_suff = nxt[suff][digit];
			int new_beauty = beauty + v[new_suff];
			int new_less_r = less_r || digit < R[i] - '0';
			if (new_beauty <= K) add(dp[i + 1][new_suff][new_beauty][new_less_r], dp[i][suff][beauty][less_r]);
		}
	}
	int res = 0;
	REP(suff, X.size() + 1) REP(beauty, K + 1) REP(less_r, 2) add(res, dp[R.size()][suff][beauty][less_r]);
	return res;
}

void process(void) {
	kmp[0] = 0;
	nxt[0][X[0] - '0'] = 1;
	FOR(i, 1, X.size()) {
		kmp[i] = i == 1 ? 0 : nxt[kmp[i - 1]][X[i - 1] - '0'];
		v[i] += v[kmp[i]];
		REP(j, 10) nxt[i][j] = j == X[i] - '0' ? i + 1 : nxt[kmp[i]][j];
	}
	FORD(i, (int) L.size() - 1, 0) {
		--L[i];
		if (L[i] < '0') L[i] += 10;
		else break;
	}
	cout << (solve(R) - solve(L) + MOD) % MOD << '\n';
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
	file("badnum");
	init();
	process();
	return (0^0);
}