#ifdef ONLINE_JUDGE #pragma GCC target("avx2,avx") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #endif #include using namespace std; using ll = long long; using ull = unsigned long long; using i128 = __int128_t; using pii = pair; using pll = pair; #define rep(i, n) for (int i = 0; i < (n); i++) #define all(x) (x).begin(), (x).end() constexpr char ln = '\n'; template inline int SZ(Container& v) { return int(v.size()); } template inline void UNIQUE(vector& v) { v.erase(unique(v.begin(), v.end()), v.end()); } template inline bool chmax(T1& a, T2 b) { if (a < b) {a = b; return true ;} return false ;} template inline bool chmin(T1& a, T2 b) { if (a > b) {a = b; return true ;} return false ;} struct fast_ios { fast_ios() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_; //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// //必要に応じて、len 、par などの情報を持たせる template struct AhoCorasick { struct State { map nex; int link, last; State() : link(0), last(0) {} }; vector node; AhoCorasick() { node.emplace_back(); node[0].link = -1; } int process(int cur, Char c) { while (~cur and !node[cur].nex.count(c)) cur = node[cur].link; if (~cur) return node[cur].nex[c]; return 0; } int addChar(Char c, int cur = 0) { if (!node[cur].nex.count(c)) { node[cur].nex[c] = node.size(); node.emplace_back(); } return node[cur].nex[c]; } template int addString(const String& s) { int cur = 0; for(const Char& c : s) { cur = addChar(cur,c); } node[cur].last = 1; return cur; } void build() { queue que; for (auto& p : node[0].nex) que.emplace(p.second); while (!que.empty()) { int cur = que.front(); que.pop(); for(auto& [c,nex] : node[cur].nex) { node[nex].link = process(node[cur].link,c); node[nex].last |= node[node[nex].link].last; que.emplace(nex); } } } State& operator[](int v) { return node[v]; } int size() { return int(node.size()); } }; ///////////////////////////////////////////////////////////////////////////////////////// template struct ModInt { public: static constexpr int mod() { return m; } static ModInt raw(int v) { ModInt x; x._v = v; return x; } ModInt() : _v(0) {} ModInt(long long v) { long long x = (long long)(v % (long long)(umod())); if (x < 0) x += umod(); _v = (unsigned int)(x); } unsigned int val() const { return _v; } ModInt& operator++() { _v++; if (_v == umod()) _v = 0; return *this; } ModInt& operator--() { if (_v == 0) _v = umod(); _v--; return *this; } ModInt operator++(int) { ModInt result = *this; ++*this; return result; } ModInt operator--(int) { ModInt result = *this; --*this; return result; } ModInt& operator+=(const ModInt& rhs) { _v += rhs._v; if (_v >= umod()) _v -= umod(); return *this; } ModInt& operator-=(const ModInt& rhs) { _v -= rhs._v; if (_v >= umod()) _v += umod(); return *this; } ModInt& operator*=(const ModInt& rhs) { unsigned long long z = _v; z *= rhs._v; _v = (unsigned int)(z % umod()); return *this; } ModInt& operator^=(long long n) { ModInt x = *this; *this = 1; if (n < 0) x = x.inv(), n = -n; while (n) { if (n & 1) *this *= x; x *= x; n >>= 1; } return *this; } ModInt& operator/=(const ModInt& rhs) { return *this = *this * rhs.inv(); } ModInt operator+() const { return *this; } ModInt operator-() const { return ModInt() - *this; } ModInt pow(long long n) const { ModInt r = *this; r ^= n; return r; } ModInt inv() const { int a = _v, b = umod(), y = 1, z = 0, t; for (; ; ) { t = a / b; a -= t * b; if (a == 0) { assert(b == 1 || b == -1); return ModInt(b * z); } y -= t * z; t = b / a; b -= t * a; if (b == 0) { assert(a == 1 || a == -1); return ModInt(a * y); } z -= t * y; } } friend ModInt operator+(const ModInt& lhs, const ModInt& rhs) { return ModInt(lhs) += rhs; } friend ModInt operator-(const ModInt& lhs, const ModInt& rhs) { return ModInt(lhs) -= rhs; } friend ModInt operator*(const ModInt& lhs, const ModInt& rhs) { return ModInt(lhs) *= rhs; } friend ModInt operator/(const ModInt& lhs, const ModInt& rhs) { return ModInt(lhs) /= rhs; } friend ModInt operator^(const ModInt& lhs, long long rhs) { return ModInt(lhs) ^= rhs; } friend bool operator==(const ModInt& lhs, const ModInt& rhs) { return lhs._v == rhs._v; } friend bool operator!=(const ModInt& lhs, const ModInt& rhs) { return lhs._v != rhs._v; } friend ModInt operator+(long long lhs, const ModInt& rhs) { return (ModInt(lhs) += rhs); } friend ModInt operator-(long long lhs, const ModInt& rhs) { return (ModInt(lhs) -= rhs); } friend ModInt operator*(long long lhs, const ModInt& rhs) { return (ModInt(lhs) *= rhs); } friend ostream &operator<<(ostream& os, const ModInt& rhs) { return os << rhs._v; } private: unsigned int _v; static constexpr unsigned int umod() { return m; } }; constexpr int MOD = 1000000007; //constexpr int MOD = 998244353; using mint = ModInt; void yukico1269() { ll N,L,R; cin >> N >> L >> R; AhoCorasick AC; ll f1 = 0,f2 = 1; while (true) { ll f = f1+f2; if (f > R) break; if (f >= L) { vector num; for (ll a = f; a ;) { num.emplace_back(a%10); a /= 10; } reverse(all(num)); AC.addString(num); } } AC.build(); int M = AC.size(); vector> nex(M, vector(10)); rep(i,M) { rep(j,10) { nex[i][j] = AC.process(i,j); if (AC[nex[i][j]].last) nex[i][j] = -1; } } vector dp(M); dp[0] = 1; rep(i,N) { vector ndp(M); rep(j,M) { if (dp[j]==0) continue; rep(k,10) { if (~nex[j][k]) ndp[nex[j][k]] += dp[j]; } } swap(dp,ndp); } mint ans = 0; rep(j,M) ans += dp[j]; ans--; cout << ans << ln; } int main() { yukico1269(); }