#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

const int MOD = 1e9 + 9;

int add(int a, int b) {
    if (a + b < MOD)
        return a + b;
    return a + b - MOD;
}

int sub(int a, int b) {
    if (a >= b)
        return a - b;
    return a + MOD - b;
}

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

int go[(1 << 10) + 228][10];
int dp[5050][(1 << 10) + 228];


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int N;
    string L, R;
    cin >> N >> L >> R;

    for (int mask = 0; mask < (1 << 10); ++mask) {
        go[mask][0] = mask;
        for (int i = 1; i < 10; ++i) {
            int j = i;
            while (j != -1 && !(mask & (1 << j)))
                --j;
            if (j == -1)
                go[mask][i] = mask ^ (1 << i);
            else
                go[mask][i] = mask ^ (1 << i) ^ (1 << j);
        }
    }
    for (int mask = 0; mask < (1 << 10); ++mask) {
        dp[0][mask] = __builtin_popcount(mask);
    }
    for (int len = 1; len <= N; ++len) {
        for (int mask = 0; mask < (1 << 10); ++mask) {
            for (int i = 0; i < 10; ++i)
                dp[len][mask] = add(dp[len][mask], dp[len - 1][go[mask][i]]);
        }
    }

    auto get_sum = [&](const string& mx, bool take_mx) {
        int total_shifts = 0;
        int cur_mask = 0;
        for (int i = 0; i < N; ++i) {
            int digit = mx[i] - '0';
            for (int j = 0; j < digit; ++j) {
                int tmp_mask = go[cur_mask][j];
                total_shifts = add(total_shifts, dp[N - i - 1][tmp_mask]);
            }
            cur_mask = go[cur_mask][digit];
        }
        if (take_mx)
            total_shifts = add(total_shifts, dp[0][cur_mask]);
        int ans = mul(total_shifts, 10);
        int st_digit = mx[0] - '0';
        int ten_pow = 1;
        for (int i = 0; i < N - 1; ++i)
            ten_pow = mul(ten_pow, 10);
        for (int i = 0; i < st_digit; ++i) {
            ans = sub(ans, mul(i, ten_pow));
        }
        int rest_cnt = 0;
        for (int j = 1; j < N; ++j)
            rest_cnt = add(mul(rest_cnt, 10), mx[j] - '0');
        ans = sub(ans, mul(st_digit, rest_cnt));
        if (take_mx)
            ans = sub(ans, st_digit);
        return ans;
    };
    int ans = sub(get_sum(R, true), get_sum(L, false));
    cout << ans << '\n';
    return 0;
}