#define MOD_TYPE 1 #include using namespace std; using ll = long long; constexpr ll MOD = ll(1e9 + 7); #define rep(i, n) for (int i = 0; i < int(n); ++i) template struct Fp { ll val; constexpr Fp(ll v = 0) noexcept : val(v % MOD) { if (val < 0) v += MOD; } constexpr int getmod() { return MOD; } constexpr Fp operator-() const noexcept { return val ? MOD - val : 0; } constexpr Fp operator+(const Fp &r) const noexcept { return Fp(*this) += r; } constexpr Fp operator-(const Fp &r) const noexcept { return Fp(*this) -= r; } constexpr Fp operator*(const Fp &r) const noexcept { return Fp(*this) *= r; } constexpr Fp operator/(const Fp &r) const noexcept { return Fp(*this) /= r; } constexpr Fp &operator+=(const Fp &r) noexcept { val += r.val; if (val >= MOD) val -= MOD; return *this; } constexpr Fp &operator-=(const Fp &r) noexcept { val -= r.val; if (val < 0) val += MOD; return *this; } constexpr Fp &operator*=(const Fp &r) noexcept { val = val * r.val % MOD; if (val < 0) val += MOD; return *this; } constexpr Fp &operator/=(const Fp &r) noexcept { ll a = r.val, b = MOD, u = 1, v = 0; while (b) { ll t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } val = val * u % MOD; if (val < 0) val += MOD; return *this; } constexpr bool operator==(const Fp &r) const noexcept { return this->val == r.val; } constexpr bool operator!=(const Fp &r) const noexcept { return this->val != r.val; } friend constexpr ostream &operator<<(ostream &os, const Fp &x) noexcept { return os << x.val; } friend constexpr istream &operator>>(istream &is, Fp &x) noexcept { return is >> x.val; } }; Fp modpow(const Fp &a, ll n) noexcept { if (n == 0) return 1; auto t = modpow(a, n / 2); t = t * t; if (n & 1) t = t * a; return t; } using mint = Fp; template struct AhoCorasick { struct node { // suff : 先頭の文字を最小限消してグラフに存在する頂点にするときの行先の頂点 // dict : 先頭の文字を最小限消して辞書に存在する単語にするときの行先の頂点 // depth : Trie木における深さ(省略可能) // word_index : このノードで終わる根からの単語のindex(祖先は含まない。なければ-1) // word_count : このノードで終わる単語の総数 // link : Trie及びsuffixの辺の接続先頂点(なければ-1) int suff = -1, dict = -1, depth = 0; int word_index = -1, word_count = 0; int link[ALPHABET]; node() { fill(link, link + ALPHABET, -1); } int &operator[](char c) { return link[c - MIN_CHAR]; } }; // nodes : 頂点集合 // W : 現在の単語数 // word_location : 各単語の(単語リストの)index // word_indices_by_depth : 単語のindexをdepthの降順に並べたもの // defer : 各単語のTrie木の最後の頂点のindex vector nodes; int W; vector word_location; vector word_indices_by_depth; vector defer; AhoCorasick(){}; AhoCorasick(const vector &words = {}) { build(words); } int get_or_add_child(int current, char c) { if (nodes[current][c] >= 0) return nodes[current][c]; int index = int(nodes.size()); nodes[current][c] = index; nodes.emplace_back(); nodes.back().depth = nodes[current].depth + 1; return index; } int add_word(const string &word, int word_index) { assert(!nodes.empty()); int current = 0; for (char c : word) current = get_or_add_child(current, c); if (nodes[current].word_index < 0) nodes[current].word_index = word_index; nodes[current].word_count++; return current; } // locationからcを追加したときの行き先 O(1) int get_suffix_link(int location, char c) const { if (location >= 0) location = nodes[location].link[c - MIN_CHAR]; return max(location, 0); } void build(const vector &words) { nodes = {node()}; W = int(words.size()); word_location.resize(W); defer.resize(W); int max_depth = 0; for (int i = 0; i < W; i++) { word_location[i] = add_word(words[i], i); max_depth = max(max_depth, int(words[i].size())); defer[i] = nodes[word_location[i]].word_index; } word_indices_by_depth.resize(W); vector depth_freq(max_depth + 1, 0); for (int i = 0; i < W; i++) depth_freq[words[i].size()]++; for (int i = max_depth - 1; i >= 0; i--) depth_freq[i] += depth_freq[i + 1]; for (int i = 0; i < W; i++) word_indices_by_depth[--depth_freq[words[i].size()]] = i; vector q = {0}; for (int i = 0; i < int(q.size()); i++) { int current = q[i]; for (char c = MIN_CHAR; c < MIN_CHAR + ALPHABET; c++) { int &index = nodes[current][c]; if (index >= 0) { int suffix_parent = get_suffix_link(nodes[current].suff, c); nodes[index].suff = suffix_parent; nodes[index].word_count += nodes[suffix_parent].word_count; nodes[index].dict = nodes[suffix_parent].word_index < 0 ? nodes[suffix_parent].dict : suffix_parent; q.push_back(index); } else { index = get_suffix_link(nodes[current].suff, c); } } } } }; int main() { ll n, l, r; cin >> n >> l >> r; vector F; ll f = 1, f1 = 1, f2 = 0; while (f <= r) { if (f >= l) F.push_back(to_string(f)); ll temp = f + f1; f2 = f1, f1 = f, f = temp; } AhoCorasick<'0', 10> aho(F); mint dp[5010][1010] = {}; dp[0][0] = 1; rep(i, n) rep(state, aho.nodes.size()) rep(j, 10) { int next_state = aho.get_suffix_link(state, '0' + j); if (aho.nodes[next_state].word_count == 0) dp[i + 1][next_state] += dp[i][state]; } mint sum = 0; rep(state, aho.nodes.size()) sum += dp[n][state]; sum -= 1; cout << sum << "\n"; }