#pragma GCC optimize("fast-math") // begin "cp-lib/prelude.hpp" #include #ifdef LOCAL # include #else # define dbg(...) do {} while (0) #endif #define cp_lib_4th(_1, _2, _3, x, ...) x #define cp_lib_rep(i, l, r) for (int i = (l); (i) < (r); ++(i)) #define cp_lib_rep0(i, r) cp_lib_rep(i, 0, r) #define rep(...) cp_lib_4th(__VA_ARGS__, cp_lib_rep, cp_lib_rep0, _)(__VA_ARGS__) #define cp_lib_repr(i, r, l, ...) for (int i = (r); (i) >= (l); --(i)) #define repr(...) cp_lib_repr(__VA_ARGS__, 0) #define all(a) ::begin(a),::end(a) #define trav(a, b) for (auto&& a : (b)) using namespace std; using ll = long long; using ld = long double; [[maybe_unused]] static constexpr int INF = int(1e9 + 5); [[maybe_unused]] static constexpr ll INFL = ll(INF) * INF; template int sz(const C& c) { return int(::size(c)); } // end "cp-lib/prelude.hpp" // begin "cp-lib/io.hpp" // begin "_assert.hpp" #ifdef CP_LIB_DEBUG #define cp_lib_assert(expr) \ do { if (!(expr)) { \ ::cerr << "assertion failed: " << #expr << " (" << __FILE__ << ':' << __LINE__ << ")\n"; \ ::abort(); \ } } while (0) #else #define cp_lib_assert(expr) #endif // end "_assert.hpp" // begin "modint/_detect.hpp" namespace cp_lib_modint { struct ModIntTag {}; } // end "modint/_detect.hpp" #include namespace cp_lib_io { constexpr int BUF_SIZE = 1 << 20; array ibuf, obuf; char *iptr = data(ibuf), *iend = iptr, *optr = data(obuf); template struct is_tuple_like : false_type {}; template struct is_tuple_like>> : true_type {}; template struct is_std_array : false_type {}; template struct is_std_array> : true_type {}; void flush() { write(STDOUT_FILENO, begin(obuf), optr - begin(obuf)); optr = begin(obuf); } void ensure_write(int l) { if (end(obuf) - optr < l) flush(); } int _flush_atexit = []{ atexit(flush); return 0; }(); void refill() { memmove(begin(ibuf), iptr, iend - iptr); iend -= iptr - begin(ibuf); iptr = begin(ibuf); iend += read(STDIN_FILENO, iend, end(ibuf) - iend); } void skip_ensure_read(int l) { do { while (iptr != iend && *iptr <= ' ') ++iptr; if (iend - iptr < l) refill(); } while (*iptr <= ' '); } template >> void print(T&& val) { if constexpr (is_same_v) ensure_write(2), *optr++ = val; else if constexpr (is_integral_v && !is_same_v) { ensure_write(numeric_limits::digits10 + 1 + is_signed_v); if (val < 0) { *optr++ = '-'; print(make_unsigned_t(-make_unsigned_t(val))); return; } array tmp; char* tptr = end(tmp); remove_const_t val_copy = val; do { *--tptr = char('0' + val_copy % 10), val_copy /= 10; } while (val_copy); memcpy(optr, tptr, end(tmp) - tptr); optr += end(tmp) - tptr; #if __cpp_lib_to_chars >= 201611 } else if constexpr (is_floating_point_v) { ensure_write(64); auto res = to_chars(optr, end(obuf), val, chars_format::fixed, 30); cp_lib_assert(res.ec == errc()); optr = res.ptr; #endif } else if constexpr (is_convertible_v) { string_view sv(val); if (sz(sv) + 1 <= end(obuf) - optr) memcpy(optr, data(sv), sz(sv)), optr += sz(sv); else flush(), write(STDOUT_FILENO, data(sv), sz(sv)); } else { if constexpr (is_same_v || is_same_v::reference>) print(int(val)); else if constexpr (is_base_of_v) print(decltype(T2::mod())(val)); else if constexpr (is_tuple_like() && !is_std_array()) apply([](auto&&... items) { (print(items), ...); }, forward(val)); else trav(item, val) print(item); return; } *optr++ = ' '; } template void read(T& val) { if constexpr (is_same_v) skip_ensure_read(1), val = *iptr++; else if constexpr (is_same_v || is_same_v::reference>) { uint8_t ival; read(ival), val = bool(ival); } else if constexpr (is_base_of_v) { ll ival; read(ival); val = T(ival); } else if constexpr (is_integral_v) { skip_ensure_read(numeric_limits::digits10 + 1 + is_signed_v); if (is_signed_v && *iptr == '-') { ++iptr; make_unsigned_t uval; read(uval); val = T(-uval); } else { val = 0; while (iptr != iend && *iptr > ' ') val = T(10 * val + (*iptr++ - '0')); } #if __cpp_lib_to_chars >= 201611 } else if constexpr (is_floating_point_v) { skip_ensure_read(128); auto res = from_chars(iptr, iend, val); assert(res.ec == errc()); iptr = const_cast(res.ptr); #endif } else if constexpr (is_same_v) { val = string(); skip_ensure_read(1); do { auto* after = iptr; while (after != iend && *after > ' ') ++after; copy(iptr, after, back_inserter(val)); if ((iptr = after) == iend) refill(); else break; } while (iptr != iend); } else if constexpr (is_tuple_like() && !is_std_array()) apply([](auto&... items) { (read(items), ...); }, val); else trav(item, val) read(item); } } using cp_lib_io::flush; template void print(Args&&... args) { (cp_lib_io::print(forward(args)), ...); } template void println(Args&&... args) { if (sizeof...(Args) > 0) (cp_lib_io::print(forward(args)), ...), *(cp_lib_io::optr - 1) = '\n'; else cp_lib_io::ensure_write(1), *cp_lib_io::optr++ = '\n'; } template void printlns(Args&&... args) { ((cp_lib_io::print(forward(args)), *(cp_lib_io::optr - 1) = '\n'), ...); } template void read(Args&... args) { (cp_lib_io::read(args), ...); } // end "cp-lib/io.hpp" // begin "cp-lib/modint/static-montgomery.hpp" // begin "_base.hpp" // begin "../math/ext-gcd.hpp" template constexpr enable_if_t, array> ext_gcd(I a, I b) { I x(1), y(0), x1(0), y1(1); while (b) { I t = a / b; tie(x, x1) = pair(x1, x - t * x1); tie(y, y1) = pair(y1, y - t * y1); tie(a, b) = pair(b, a - t * b); } return {a, x, y}; } // end "../math/ext-gcd.hpp" namespace cp_lib_modint { template struct Base : ModIntTag { static_assert(is_same_v || is_same_v); friend constexpr Self operator+(Self l, Self r) { return l += r; } friend constexpr Self operator-(Self l, Self r) { return l -= r; } friend constexpr Self operator*(Self l, Self r) { return l *= r; } friend constexpr Self operator/(Self l, Self r) { return l * r.inv(); } friend constexpr Self& operator/=(Self& l, Self r) { return l *= r.inv(); } friend constexpr Self operator+(Self x) { return x; } friend constexpr Self operator-(Self x) { return Self(0) - x; } friend constexpr Self& operator++(Self& x) { return x += Self(1); } friend constexpr Self& operator--(Self& x) { return x -= Self(1); } friend constexpr Self operator++(Self& x, int) { auto y = x; ++x; return y; } friend constexpr Self operator--(Self& x, int) { auto y = x; --x; return y; } #define CP_LIB_DEF(op) \ template , int> = 0> \ friend constexpr auto operator op(T l, Self r) { return Self(l) op r; } CP_LIB_DEF(==) CP_LIB_DEF(!=) CP_LIB_DEF(<) CP_LIB_DEF(+) CP_LIB_DEF(-) CP_LIB_DEF(*) CP_LIB_DEF(/) #undef CP_LIB_DEF template constexpr enable_if_t, Self> pow(T e) const { Self r(1), b(*(Self*)(this)); for (; e; b *= b, e >>= 1) if (e & 1) r *= b; return r; } constexpr optional try_inv() const { if (Self::is_prime()) return *(Self*)this == Self() ? nullopt : optional(pow(Self::mod() - 2)); auto [g, x, _] = ext_gcd(ll(*(Self*)this), ll(Self::mod())); return (abs(g) == 1 ? optional(Self(x)) : nullopt); } constexpr Self inv() const { if (Self::is_prime()) return pow(Self::mod() - 2); auto [g, x, _] = ext_gcd(ll(*(Self*)this), ll(Self::mod())); cp_lib_assert(abs(g) == 1); return x; } friend ostream& operator<<(ostream& out, Self m) { return out << uint64_t(m); } friend istream& operator>>(istream& in, Self& m) { ll x; in >> x; m = x; return in; } protected: Int i = 0; }; template using Wide = conditional_t, unsigned __int128, uint64_t>; } struct ModIntRaw {}; // end "_base.hpp" namespace cp_lib_modint { template class StaticMontgomery : public Base, Int> { static_assert(Mod % 2 && Mod < (1ull << (sizeof(Int) * 8 - 2))); static constexpr Int INV = []{ Int inv = Mod; rep(_, __builtin_ctz(sizeof(Int) * 8) - 1) inv *= 2 - Mod * inv; return inv; }(); static constexpr Int R2 = Int(-Wide(Mod) % Mod); static constexpr Int reduce(Wide x) { return Int((x - Int(x) * INV * Wide(Mod))>> (sizeof(Int) * 8)) + Mod; } constexpr Int norm(Int x) const { return x >= Mod ? x - Mod : x; } public: static constexpr Int mod() { return Mod; } static constexpr bool is_prime() { return IsPrime; } StaticMontgomery() = default; template , int> = 0> constexpr StaticMontgomery(T x) { this->i = reduce(Wide(uint64_t(x) % Mod) * R2); } template , int> = 0> constexpr StaticMontgomery(T x) { this->i = reduce(Wide(ll(x) % ll(Mod) + ll(Mod)) * R2); } constexpr StaticMontgomery(Int x, ModIntRaw) { this->i = x; } template , int> = 0> constexpr explicit operator T() const { return T(norm(reduce(this->i))); } constexpr bool operator==(StaticMontgomery r) const { return norm(this->i) == norm(r.i); } constexpr bool operator!=(StaticMontgomery r) const { return norm(this->i) != norm(r.i); } constexpr bool operator<(StaticMontgomery r) const { return norm(this->i) < norm(r.i); } constexpr StaticMontgomery& operator+=(StaticMontgomery r) { if ((this->i += r.i) >= 2 * Mod) this->i -= 2 * Mod; return *this; } constexpr StaticMontgomery& operator-=(StaticMontgomery r) { if (make_signed_t(this->i -= r.i) < 0) this->i += 2 * Mod; return *this; } constexpr StaticMontgomery& operator*=(StaticMontgomery r) { return *this = {reduce(Wide(this->i) * r.i), {}}; } }; } template using StaticMontgomeryInt = cp_lib_modint::StaticMontgomery; template using StaticMontgomeryInt64 = cp_lib_modint::StaticMontgomery; // end "cp-lib/modint/static-montgomery.hpp" template struct Trie { static constexpr bool Sparse = (K == -1); vector> t{1}; vector cnt = {INF}; size_t size() const { return ::size(t); } int next(int v, int c) const { return t[v][c]; } template ::value_type> int add(It it, ItEnd it_end, T base = (is_same_v ? 'a' : T(0))) { int v = 0; for (; it != it_end; ++it) { if (!t[v][*it - base]) t[v][*it - base] = sz(t), t.emplace_back(), cnt.emplace_back(); v = t[v][*it - base]; ++cnt[v]; } return v; } template ::value_type> void remove(It it, ItEnd it_end, T base = (is_same_v ? 'a' : T(0))) { int v = 0; for (; it != it_end && --cnt[next(v, *it - base)]; v = next(v, *it++ - base)) cp_lib_assert(next(v, *it - base)); if (it != it_end) t[v][*it - base] = 0; } }; template class BitTrie : public Trie<2> { array bits; void to_bits(uint64_t x) { rep(i, W) bits[W - 1 - i] = (x >> i) & 1; } template uint64_t xor_eval(uint64_t x) const { uint64_t ans = 0; for (int i = W - 1, v = 0, bit = int((x >> i) & 1); i >= 0; bit = int((x >> --i) & 1)) { if (next(v, bit ^ Max)) v = next(v, bit ^ Max), ans ^= (uint64_t(Max) << i); else v = next(v, !bit ^ Max), ans ^= (uint64_t(!Max) << i); } return ans; } public: uint64_t xor_min(uint64_t x) const { return xor_eval(x); } uint64_t xor_max(uint64_t x) const { return xor_eval(x); } int add(uint64_t x) { to_bits(x); return Trie<2>::add(all(bits)); } void remove(uint64_t x) { to_bits(x); Trie<2>::remove(all(bits)); } }; template struct AhoCorasick : Trie { template void build(F&& f) { queue> q; q.push({0, -1, 0, -1}); while (sz(q)) { auto [v, c, p, plink] = q.front(); q.pop(); int link = (p ? this->next(plink, c) : 0); rep(i, K) { if (this->next(v, i)) q.push({this->next(v, i), i, v, link}); else this->t[v][i] = (v ? this->next(link, i) : 0); } if (v) f(v, link, c, p); } } }; int main() { int n; ll l, r; read(n, l, r); vector fib = {0ll, 1ll}; while (fib.back() <= r) fib.push_back(fib.back() + fib[sz(fib) - 2]); AhoCorasick<10> ac; vector is_end; trav(fi, fib) { if (fi < l || r < fi) continue; auto s = to_string(fi); int v = ac.add(all(s), '0'); is_end.resize(sz(ac)); is_end[v] = true; } ac.build([&](int v, int link, int, int) { is_end[v] = is_end[v] || is_end[link]; }); int m = sz(ac); using MI = StaticMontgomeryInt; vector dp(n + 1, vector(m, MI(0))); dp[0][0] = 1; rep(i, n) rep(j, m) rep(k, 10) if (!is_end[j]) dp[i + 1][ac.next(j, k)] += dp[i][j]; MI ans = 0; rep(i, m) if (!is_end[i]) ans += dp[n][i]; println(ans - 1); }