#include <array>
#include <iostream>

using namespace std;

constexpr int M = 1 << 9, mod = 1e9 + 9;

auto& mul(auto&& a, auto b) { return a = a * (uint64_t)b % mod; }
auto& add(auto&& a, auto b) { return a -= (a += b) >= mod? mod: 0; }
int fpow(int a, int b) { for (int r = 1; ; b /= 2, mul(a, a)) if (!b) return r; else if (b % 2) mul(r, a); }
int f(int i, int j) { return (i & i - (1 << j) | 1 << j) & M - 1; }

array<int, M> dp, ndp;

int solve(string s, bool sub) {
  for (auto& c: s) c -= '0';
  for (int i = s.size(); sub; ) if (!i--) return 0; else if (s[i]--) break; else s[i] = 9;
  dp = {};
  int p = 0;
  for (auto c: s) {
    for (int i = 0; i < M; ++i) for (int d = 10; d--; ) add(ndp[f(i, d)], dp[i]);
    dp = ndp, ndp = {};
    for (int d = c = 9 - c; d++ < 9; ) add(dp[f(p, d)], 1);
    p = f(p, c);
  }
  add(dp[p], 1);
  int ans = 0;
  for (int i = M; i--; ) add(ans, mul(__builtin_popcount(i), dp[i]));
  mul(ans, 10);
  add(ans, mul(mod - s[0] * (s[0] - 1) / 2, fpow(10, s.size() - 1)));
  p = 0;
  for (auto c: s.substr(1)) p = (p * 10ull + c) % mod;
  add(ans, mul(mod - s[0], p + 1));
  return ans;
}

int main() {
  string l, r; cin >> l >> l >> r;
  cout << add(solve(r, 0), mod - solve(l, 1)) << '\n';
}

answer.code: In function ‘auto& mul(auto:16&&, auto:17)’:
answer.code:8:47: error: ‘uint64_t’ was not declared in this scope
    8 | auto& mul(auto&& a, auto b) { return a = a * (uint64_t)b % mod; }
      |                                               ^~~~~~~~
answer.code:3:1: note: ‘uint64_t’ is defined in header ‘<cstdint>’; did you forget to ‘#include <cstdint>’?
    2 | #include <iostream>
  +++ |+#include <cstdint>
    3 | 
answer.code:8:56: error: expected ‘;’ before ‘b’
    8 | auto& mul(auto&& a, auto b) { return a = a * (uint64_t)b % mod; }
      |                                                        ^
      |                                                        ;