#include <bits/stdc++.h>
using namespace std;

const int N = 5005;
const int mod = 1e9 + 9;

int n, cnt, a[N], ns[1 << 10][10], dp[N][1 << 10][2];
string L, R;
ofstream outf("j.out");

int qpow(int x, int y) {
	int res = 1;
	while (y) {
		if (y & 1) {
			res = 1ll * res * x % mod;
		}
		x = 1ll * x * x % mod;
		y >>= 1;
	}
	return res;
}

long long query(string x) {
	for (int i = 1; i <= n; i++) {
		a[i] = x[i - 1] - '0';
	}
	memset(dp, 0, sizeof(dp));
	dp[0][0][1] = 1;
	for (int i = 0; i < n; i++) {
		for (int s = 0; s < 1 << 10; s++) {
			for (int lim = 0; lim < 2; lim++) {
				if (!dp[i][s][lim]) {
					continue;
				}
				for (int j = 0; j <= (lim ? a[i + 1] : 9); j++) {
					int s_ = ns[s][j], lim_ = lim & j == a[i + 1];
					dp[i + 1][s_][lim_] = (dp[i + 1][s_][lim_] + dp[i][s][lim]) % mod;
				}
			}
		}
	}
	long long res = 0;
	for (int s = 0; s < 1 << 10; s++) {
		res = (res + 1ll * (dp[n][s][0] + dp[n][s][1]) * (__builtin_popcount(s) - (s & 1)) % mod * 10 % mod) % mod;
	}
	for (int i = 0; i < a[1]; i++) {
		res = (res - 1ll * i * qpow(10, n - 1) % mod + mod) % mod;
	}
	int val = 0;
	for (int i = 2; i <= n; i++) {
		val = (10ll * val + a[i]) % mod;
	}
	val = (val + 1) % mod;
	res = (res - 1ll * val * a[1] % mod + mod) % mod;
	return res;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	for (int s = 0; s < 1 << 10; s++) {
		for (int i = 0; i < 10; i++) {
			ns[s][i] = s ^ 1 << i;
			for (int j = i; j >= 0; j--) {
				if (s >> j & 1) {
					ns[s][i] ^= 1 << j;
					break;
				}
			}
		}
	}
	cin >> n >> L >> R;
	int now = n - 1;
	while (now >= 0 && L[now] == '0') {
		now--;
	}
	if (now == -1) {
		cout << query(R) << '\n';
	}
	else {
		L[now]--;
		for (int j = now + 1; j < n; j++) {
			L[j] = '9';
		}
		cout << (query(R) - query(L) + mod) % mod << '\n';
	}

	return 0;
}