#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e5 + 9, Mod = 1e9 + 7; int fpow(int a, int b = Mod - 2) { int res = 1; while (b) { if (b & 1) res = 1ll * res * a % Mod; a = 1ll * a * a % Mod, b >>= 1; } return res; } int n, m, cnt, ans, L[N], R[N], C[19][19], F[N][19]; bool vis[19]; int f(int x, int y) { // x -> n, y -> m int res = 0; for (int i = 0; i <= y; i++) { int now = 1ll * C[y][i] * fpow(y - i, x) % Mod; res = (i & 1 ? (res - now + Mod) % Mod : (res + now) % Mod); } return res; } int vis1[N], cnt1; signed main() { for (int i = 0; i <= 10; i++) { C[i][0] = C[i][i] = 1; for (int j = 1; j < i; j++) { C[i][j] = C[i - 1][j] + C[i - 1][j - 1]; } } scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%1d", &L[i]); for (int i = 1; i <= n; i++) scanf("%1d", &R[i]); scanf("%d", &m); for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) F[i][j] = f(i, j); } int x = 1; while (x <= n && L[x] == R[x]) { if (!vis[L[x]]) cnt++; vis[L[x++]] = 1; } if (x > n) { if (cnt == m) printf("1\n"); else printf("0\n"); fclose(stdin), fclose(stdout); return 0; } for (int i = L[x] + 1; i < R[x]; i++) { int _cnt = cnt + (int)(!vis[i]); if (_cnt > m) continue; for (int j = 0; j <= _cnt; j++) { ans = (ans + 1ll * C[10 - _cnt][m - _cnt] * C[_cnt][j] % Mod * F[n - x][m - _cnt + j]) % Mod; } } for (int i = 0; i <= 9; i++) vis1[i] = vis[i]; cnt1 = cnt; if (!vis1[L[x]]) cnt1++; vis1[L[x]] = 1; for (int _x = x + 1; _x <= n; _x++) { int t0 = 0, t1 = 0, s = 0; for (int i = L[_x] + 1; i <= 9; i++) { if (vis1[i]) t0++; else t1++; } if (cnt1 <= m) { for (int j = 0; j <= cnt1; j++) { s = (s + 1ll * C[10 - cnt1][m - cnt1] * C[cnt1][j] % Mod * F[n - _x][m - cnt1 + j]) % Mod; } ans = (ans + 1ll * t0 * s) % Mod, s = 0; } if (cnt1 < m) { int _cnt = cnt1 + 1; for (int j = 0; j <= _cnt; j++) { s = (s + 1ll * C[10 - _cnt][m - _cnt] * C[_cnt][j] % Mod * F[n - _x][m - _cnt + j]) % Mod; } ans = (ans + 1ll * t1 * s) % Mod; } if (!vis1[L[_x]]) cnt1++; vis1[L[_x]] = 1; } if (cnt1 == m) ans++, ans %= Mod; for (int i = 0; i <= 9; i++) vis1[i] = vis[i]; cnt1 = cnt; if (!vis1[R[x]]) cnt1++; vis1[R[x]] = 1; for (int _x = x + 1; _x <= n; _x++) { int t0 = 0, t1 = 0, s = 0; for (int i = 0; i < R[_x]; i++) { if (vis1[i]) t0++; else t1++; } if (cnt1 <= m) { for (int j = 0; j <= cnt1; j++) { s = (s + 1ll * C[10 - cnt1][m - cnt1] * C[cnt1][j] % Mod * F[n - _x][m - cnt1 + j]) % Mod; } ans = (ans + 1ll * t0 * s) % Mod, s = 0; } if (cnt1 < m) { int _cnt = cnt1 + 1; for (int j = 0; j <= _cnt; j++) { s = (s + 1ll * C[10 - _cnt][m - _cnt] * C[_cnt][j] % Mod * F[n - _x][m - _cnt + j]) % Mod; } ans = (ans + 1ll * t1 * s) % Mod; } if (!vis1[R[_x]]) cnt1++; vis1[R[_x]] = 1; } if (cnt1 == m) ans++, ans %= Mod; printf("%d\n", ans); return 0; }