#line 1 "main.cpp" #include #line 2 "/home/user/Library/utils/macros.hpp" #define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i)) #define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i)) #define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i)) #define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i)) #define ALL(x) std::begin(x), std::end(x) #line 4 "/home/user/Library/modulus/modpow.hpp" inline int32_t modpow(uint_fast64_t x, uint64_t k, int32_t MOD) { assert (/* 0 <= x and */ x < (uint_fast64_t)MOD); uint_fast64_t y = 1; for (; k; k >>= 1) { if (k & 1) (y *= x) %= MOD; (x *= x) %= MOD; } assert (/* 0 <= y and */ y < (uint_fast64_t)MOD); return y; } #line 5 "/home/user/Library/modulus/modinv.hpp" inline int32_t modinv_nocheck(int32_t value, int32_t MOD) { assert (0 <= value and value < MOD); if (value == 0) return -1; int64_t a = value, b = MOD; int64_t x = 0, y = 1; for (int64_t u = 1, v = 0; a; ) { int64_t q = b / a; x -= q * u; std::swap(x, u); y -= q * v; std::swap(y, v); b -= q * a; std::swap(b, a); } if (not (value * x + MOD * y == b and b == 1)) return -1; if (x < 0) x += MOD; assert (0 <= x and x < MOD); return x; } inline int32_t modinv(int32_t x, int32_t MOD) { int32_t y = modinv_nocheck(x, MOD); assert (y != -1); return y; } #line 6 "/home/user/Library/modulus/mint.hpp" /** * @brief quotient ring / 剰余環 $\mathbb{Z}/n\mathbb{Z}$ */ template struct mint { int32_t value; mint() : value() {} mint(int64_t value_) : value(value_ < 0 ? value_ % MOD + MOD : value_ >= MOD ? value_ % MOD : value_) {} mint(int32_t value_, std::nullptr_t) : value(value_) {} explicit operator bool() const { return value; } inline mint operator + (mint other) const { return mint(*this) += other; } inline mint operator - (mint other) const { return mint(*this) -= other; } inline mint operator * (mint other) const { return mint(*this) *= other; } inline mint & operator += (mint other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; } inline mint & operator -= (mint other) { this->value -= other.value; if (this->value < 0) this->value += MOD; return *this; } inline mint & operator *= (mint other) { this->value = (uint_fast64_t)this->value * other.value % MOD; return *this; } inline mint operator - () const { return mint(this->value ? MOD - this->value : 0, nullptr); } inline bool operator == (mint other) const { return value == other.value; } inline bool operator != (mint other) const { return value != other.value; } inline mint pow(uint64_t k) const { return mint(modpow(value, k, MOD), nullptr); } inline mint inv() const { return mint(modinv(value, MOD), nullptr); } inline mint operator / (mint other) const { return *this * other.inv(); } inline mint & operator /= (mint other) { return *this *= other.inv(); } }; template mint operator + (int64_t value, mint n) { return mint(value) + n; } template mint operator - (int64_t value, mint n) { return mint(value) - n; } template mint operator * (int64_t value, mint n) { return mint(value) * n; } template mint operator / (int64_t value, mint n) { return mint(value) / n; } template std::istream & operator >> (std::istream & in, mint & n) { int64_t value; in >> value; n = value; return in; } template std::ostream & operator << (std::ostream & out, mint n) { return out << n.value; } #line 4 "main.cpp" using namespace std; // $ ghci // Prelude> let fib = [1, 1] ++ zipWith (+) fib (tail fib) in takeWhile (<= 10 ^ 18) fib int64_t fib[] = {1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,2111485077978050,3416454622906707,5527939700884757,8944394323791464,14472334024676221,23416728348467685,37889062373143906,61305790721611591,99194853094755497,160500643816367088,259695496911122585,420196140727489673,679891637638612258}; constexpr int64_t MOD = 1000000007; mint solve(int n, int64_t l, int64_t r) { vector forbidden; for (int64_t fib_i : fib) { if (l <= fib_i and fib_i < r) { forbidden.push_back(fib_i); } } vector patterns; for (int64_t f : forbidden) { string s; while (f) { s.push_back('0' + f % 10); f /= 10; } reverse(ALL(s)); bool found = false; for (const string& pat : patterns) { if (pat.find(s) != string::npos) { found = true; } } if (not found) { patterns.push_back(s); } } cerr << "patterns.size() = " << patterns.size() << endl; auto check = [&](const string& s) { for (const string& pat : patterns) { if (s.find(pat) != string::npos) { return false; } } return true; }; auto simplify = [&](string s) { while (true) { for (const string& pat : patterns) { if (pat.find(s) == 0) { return s; } } s = s.substr(1); } }; unordered_map words; vector > g; auto go = [&](auto&& go, string s) { if (words.count(s)) return; words.emplace(s, words.size()); g.emplace_back(); REP3 (c, '0', '9' + 1) { string t = s + string(1, c); if (not check(t)) continue; t = simplify(t); go(go, t); g[words[s]].push_back(words[t]); } }; go(go, ""); // dp vector > cur(words.size()); cur[0] += 1; REP (iteration, n) { // cerr << "iteration = " << iteration << ": cur.size() = " << cur.size() << endl; vector > prv(words.size()); cur.swap(prv); REP (i, words.size()) { for (int j : g[i]) { cur[j] += prv[i]; } } } mint ans = 0; REP (i, words.size()) { ans += cur[i]; } ans -= 1; // for 0 return ans; } // generated by online-judge-template-generator v4.7.1 (https://github.com/online-judge-tools/template-generator) int main() { int N; int64_t L, R; cin >> N >> L >> R; ++ R; auto ans = solve(N, L, R); cout << ans << endl; return 0; }