//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef KIVI
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl

template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }

#else
#define DEBUG while (false)
#define LOG(...)
#endif

mt19937 rng(4242);

const int max_n = -1, inf = 1000111222;

int my(string s) {
    vector<bool> have(len(s));
    int res = 0;
    if(count(all(s), '0') == len(s)) return 0;
    res += 10 - (s[0] - '0');
    have[s[0] - '0'] = 1;
    for(int i = 1; i < len(s); i++) {
        bool ok = false;
        int cr = s[i] - '0';
        if(!cr) continue;
        for(int j = cr; j >= 0; j--) {
            if(have[j]) {
                have[j] = false;
                have[cr] = true;
                ok = true;
                break;
            }
        }
        if(!ok) { res += 10; have[cr] = true; }
    }
    return res;
}

pair<int, int> to_mask[(1 << 10)][10]; //new mask, cost

const int mod = 1e9 + 9;

int add(int a, int b) {
    int res = ((a + b) % mod + mod) % mod;
    return res;
}

int mul(int a, int b) {
    return (a * 1ll * b) % mod;
}

pair<int, int> dp[2][(1 << 10)], ndp[2][(1 << 10)];

int calc(string x) {
//    cout << x << '\n';
    int res = 0;
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < (1 << 10); j++) dp[i][j] = ndp[i][j] = {0, 0};
    for(int dig = 0; dig < x[0] - '0'; dig++) dp[1][(1 << dig)] = {1, 10 - dig};
    dp[0][(1 << (x[0] - '0'))] = {1, 10 - (x[0] - '0')};
    for(int i = 1; i < len(x); i++) {
        for(int was_less = 0; was_less < 2; was_less++)
            for(int was_mask = 0; was_mask < (1 << 10); was_mask++) {
                if(dp[was_less][was_mask] == pii{0, 0}) continue;
                for (int dig = 0; dig < 10; dig++) {
                    if (!was_less && dig > x[i] - '0') continue;
                    int nless = (was_less || (dig < x[i] - '0'));
                    int nmask, add_each_mask;
                    tie(nmask, add_each_mask) = to_mask[was_mask][dig];
//                    for (int I = 0; I < 10; I++) cout << (((was_mask >> I) & 1) == 1);
//                    cout << '\n';
//                    cout << dig << ' ' << add_each_mask << '\n';
//                    for (int I = 0; I < 10; I++) cout << (((nmask >> I) & 1) == 1);
//                    cout << "\n\n";
                    ndp[nless][nmask].fi = add(ndp[nless][nmask].fi, dp[was_less][was_mask].fi);
                    ndp[nless][nmask].se = add(ndp[nless][nmask].se, add(dp[was_less][was_mask].se, mul(dp[was_less][was_mask].fi, add_each_mask)));
                }
            }
        for(int A = 0; A < 2; A++)
            for(int B = 0; B < (1 << 10); B++) {
                dp[A][B] = ndp[A][B];
                ndp[A][B] = {0, 0};
            }
    }
    for(int A = 0; A < 2; A++)
        for(int B = 0; B < (1 << 10); B++)
            res = add(res, dp[A][B].se);
    return res;
}

void solve() {
    {
        for (int mask = 0; mask < (1 << 10); mask++) {
            for (int guy = 0; guy < 10; guy++) {
                if (mask == 0) to_mask[mask][guy] = {(1 << guy), 10 - guy};
                else {
                    pii to = {-1, -1};
                    for (int pr = guy; pr >= 0; pr--) {
                        if (((mask >> pr) & 1) == 1) {
                            to = {mask ^ (1 << pr) ^ (1 << guy), 0};
                            break;
                        }
                    }
                    if (to.fi == -1) to = {(mask ^ (1 << guy)), 10};
                    to_mask[mask][guy] = to;
                    if(guy == 0) to_mask[mask][guy] = {mask, 0};
                }
            }
        }
        int X; cin >> X;
        string a, b;
        cin >> a >> b;
        int ans = 0;
        ans = calc(b);
        if (count(all(a), '0') != len(a)) {
            int lst = len(a) - 1;
            while (a[lst] == '0') lst--;
            a[lst]--;
            for (int i = lst + 1; i < len(a); i++) a[i] = '9';
            ans = add(ans, mod - calc(a));
        } else ans -= 10;
        cout << ans << '\n';
    }
    if(false) {
        int X = 6;
        cin >> X;
        ll a, b;
        cin >> a >> b;
        int ans = 0;
        for (ll c = a; c <= b; c++) {
            string cur = to_string(c);
            cur = string(X - len(cur), '0') + cur;
            int res = 0;
//            cout << cur << " : ";
            while (cur != string(X, '0')) {
                res++;
                char was = cur[0];
                cur[0]++;
                if (cur[0] > '9') cur[0] = '0';
                for (int j = 1; j < len(cur); j++) {
                    if (cur[j] > was) break;
                    else if (cur[j] == was) cur[j] = cur[0];
                }
            }
            cur = to_string(c);
            cur = string(X - len(cur), '0') + cur;
//            cout << res << ' ' << my(cur) << '\n';
            if (res != my(cur)) exit(-1);
            ans += res;
        }
        cout << ans % mod << '\n';
    }
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;

//    cin >> t;

    while (t--) solve();

}

/*
KIVI
*/