// // Created by yamunaku on 2020/10/23. // #include //#include using namespace std; //using namespace atcoder; #define rep(i, n) for(int i = 0; i < (n); i++) #define repl(i, l, r) for(int i = (l); i < (r); i++) #define per(i, n) for(int i = ((n)-1); i >= 0; i--) #define perl(i, l, r) for(int i = ((r)-1); i >= (l); i--) #define all(x) (x).begin(),(x).end() #define MOD9 998244353 #define MOD 1000000007 #define IINF 1000000000 #define LINF 1000000000000000000 #define SP <<" "<< #define CYES cout<<"Yes"<; using mti = vector>; using vl = vector; using mtl = vector>; using pi = pair; using pl = pair; template using heap = priority_queue, function>; template struct TrieNode { int nxt[char_size]; int exist; ll count; bool flag; vector accept; TrieNode() : exist(0), count(0), flag(false) { memset(nxt, -1, sizeof(nxt)); } }; template struct Trie { using Node = TrieNode; vector nodes; int root; Trie() : root(0) { nodes.push_back(Node()); } void update_direct(int node, int id) { nodes[node].accept.push_back(id); } void update_child(int node, int child, int id) { ++nodes[node].exist; } void add(const string &str, int str_index, int node_index, int id) { if (str_index == str.size()) { update_direct(node_index, id); nodes[node_index].flag = true; } else { const int c = str[str_index] - margin; if (nodes[node_index].nxt[c] == -1) { nodes[node_index].nxt[c] = (int) nodes.size(); nodes.push_back(Node()); } add(str, str_index + 1, nodes[node_index].nxt[c], id); update_child(node_index, nodes[node_index].nxt[c], id); } } void add(const string &str, int id) { add(str, 0, 0, id); } void add(const string &str) { add(str, nodes[0].exist); } void query(const string &str, const function &f, int str_index, int node_index) { for (auto &idx : nodes[node_index].accept) f(idx); if (str_index == str.size()) { return; } else { const int c = str[str_index] - margin; if (nodes[node_index].nxt[c] == -1) return; query(str, f, str_index + 1, nodes[node_index].nxt[c]); } } void query(const string &str, const function &f) { query(str, f, 0, 0); } int count() const { return (nodes[0].exist); } int size() const { return ((int) nodes.size()); } }; template struct AhoCorasick : Trie { using Trie::Trie; const int FAIL = char_size; vector correct; void build(bool heavy = true) { correct.resize(this->size()); for (int i = 0; i < this->size(); i++) { correct[i] = (int) this->nodes[i].accept.size(); } queue que; for (int i = 0; i <= char_size; i++) { if (~this->nodes[0].nxt[i]) { this->nodes[this->nodes[0].nxt[i]].nxt[FAIL] = 0; que.emplace(this->nodes[0].nxt[i]); } else { this->nodes[0].nxt[i] = 0; } } while (!que.empty()) { auto &now = this->nodes[que.front()]; correct[que.front()] += correct[now.nxt[FAIL]]; que.pop(); for (int i = 0; i < char_size; i++) { if (now.nxt[i] == -1) continue; int fail = now.nxt[FAIL]; while (this->nodes[fail].nxt[i] == -1) fail = this->nodes[fail].nxt[FAIL]; this->nodes[now.nxt[i]].nxt[FAIL] = this->nodes[fail].nxt[i]; if (heavy) { auto &u = this->nodes[now.nxt[i]].accept; auto &v = this->nodes[this->nodes[fail].nxt[i]].accept; vector accept; set_union(begin(u), end(u), begin(v), end(v), back_inserter(accept)); u = accept; } que.emplace(now.nxt[i]); } } } map match(const string &str, int now = 0) { map result; for (auto &c : str) { while (this->nodes[now].nxt[c - margin] == -1) now = this->nodes[now].nxt[FAIL]; now = this->nodes[now].nxt[c - margin]; for (auto &v : this->nodes[now].accept) result[v] += 1; } return result; } pair move(const char &c, int now) { int sum = 0; while (this->nodes[now].nxt[c - margin] == -1) now = this->nodes[now].nxt[FAIL]; now = this->nodes[now].nxt[c - margin]; sum += correct[now]; return {sum, now}; } void init() { this->nodes[this->root].count = 1; } mti nxxt; void buildnexxt() { int sz = this->nodes.size(); nxxt = mti(sz, vi(10)); rep(i, sz) { rep(j, 10) { nxxt[i][j] = this->nodes[i].nxt[j]; if (nxxt[i][j] == -1) nxxt[i][j] = nxxt[this->nodes[i].nxt[FAIL]][j]; } } } ll moveone() { int sz = this->nodes.size(); vl tmp(sz, 0); rep(i, sz) { if (this->nodes[i].flag) continue; ll k = this->nodes[i].count; repl(j, 1, 10) { tmp[nxxt[i][j]] = (tmp[nxxt[i][j]] + k) % MOD; } } ll ans = 0; rep(i, sz) { if (this->nodes[i].flag) continue; ans = (ans + tmp[i]) % MOD; this->nodes[i].count = tmp[i]; } return ans; } ll moveall() { int sz = this->nodes.size(); vl tmp(sz, 0); rep(i, sz) { if (this->nodes[i].flag) continue; ll k = this->nodes[i].count; rep(j, 10) { tmp[nxxt[i][j]] = (tmp[nxxt[i][j]] + k) % MOD; } } ll ans = 0; rep(i, sz) { if (this->nodes[i].flag) continue; ans = (ans + tmp[i]) % MOD; this->nodes[i].count = tmp[i]; } return ans; } }; int main() { //CFS; int n; ll l, r; cin >> n >> l >> r; vl f(2, 1); while (f[f.size() - 2] < LINF - f[f.size() - 1]) { f.push_back(f[f.size() - 2] + f[f.size() - 1]); } AhoCorasick<10, '0'> ac; for (auto &x : f) { cout << x << endl; if (l <= x && x <= r) { ac.add(to_string(x)); } } ac.build(); ac.buildnexxt(); ac.init(); ll ans = ac.moveone(); repl(i, 1, n) ans = (ans + ac.moveall()) % MOD; cout << ans << endl; return 0; }