#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define fi first
#define se second
#define mpr make_pair

using namespace std;

const int mod = 1e9 + 9;

int add(int x, int y) {
    x += y;
    return x >= mod ? x - mod : x;
}

void adto(int &x, int y) {
    x += y;
    if (x >= mod)x -= mod;
}

int mul(int x, int y) {
    return 1ll * x * y % mod;
}

int qpow(int a, int b) {
    int ans = 1;
    while (b) {
        if (b & 1) {
            ans = mul(ans, a);
        }
        a = mul(a, a);
        b >>= 1;
    }
    return ans;
}

int n;
string L, R;

string minus1(string s) {
    int u = n - 1;
    while (s[u] == '0') {
        s[u] = '9';
        u--;
    }
    s[u]--;
    return s;
}

int calc(string s) {
    if (s == string(s.size(), '0'))return 0;
    s = " " + s;
    vector<vector<vector<int> > > f(n + 1, vector<vector<int> >(2, vector<int>(1 << 10))), cnt = f;
    if (s[1] == '0') {
        f[1][1][0] = 0;
        cnt[1][1][0] = 1;
    } else {
        f[1][0][0] = 0;
        cnt[1][0][ 0] = 1;
        for (int i = 1; i < s[1] - '0'; i++) {
            f[1][0][1 << i] = 10 - i;
            cnt[1][0][1 << i] = 1;
        }
        f[1][1][1 << (s[1] - '0')] = 10 - (s[1] - '0');
        cnt[1][1][1 << (s[1] - '0')] = 1;
    }
//    cout<<f[1][0][1]<<"afalkdsflakjdf\n";
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= 1; j++) {
            for (int k = 0; k < (1 << 10); k+=2) {
                if (cnt[i][j][k] == 0 && f[i][j][k] == 0)continue;
                int last = 0;
                for (int d = 0; d <= (j ? s[i + 1] - '0' : 9); d++) {
                    int nj = (j && d == s[i + 1] - '0');
                    if (d == 0) {
                        adto(f[i + 1][nj][k], f[i][j][k]);
                        adto(cnt[i + 1][nj][k], cnt[i][j][k]);
                    } else {
                        if (k >> d & 1)last = d;
                        if (last == 0) {
                            adto(f[i + 1][nj][k | (1 << d)], f[i][j][k]);
                            adto(f[i + 1][nj][k | (1 << d)], mul(10, cnt[i][j][k]));
                            adto(cnt[i + 1][nj][k | (1 << d)], cnt[i][j][k]);
                        } else {
                            adto(f[i + 1][nj][k ^ (1 << last) ^ (1 << d)], f[i][j][k]);
                            adto(cnt[i + 1][nj][k ^ (1 << last) ^ (1 << d)], cnt[i][j][k]);
                        }
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int j = 0; j <= 1; j++) {
        for (int k = 0; k < (1 << 10); k +=2) {
            adto(ans, f[n][j][k]);
        }
    }
    return ans;
}

void solve() {
    cin >> n >> L >> R;
    if (L == string(L.size(), '0')) {
        cout << calc(R);
    } else cout << add(calc(R), mod - calc(minus1(L)));
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t = 1;
//    cin >> t;
    while (t--)solve();
    return 0;
}