#include using namespace std; #define LOCAL #pragma region Macros typedef long long ll; #define ALL(x) (x).begin(),(x).end() const long long MOD=1000000007; // const long long MOD=998244353; const int INF=1e9; const long long IINF=1e18; const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; const char dir[4]={'D','R','U','L'}; template istream &operator>>(istream &is,vector &v){ for (T &x:v) is >> x; return is; } template ostream &operator<<(ostream &os,const vector &v){ for (int i=0;i ostream &operator<<(ostream &os,const pair &p){ os << '(' << p.first << ',' << p.second << ')'; return os; } template ostream &operator<<(ostream &os,const map &m){ os << '{'; for (auto itr=m.begin();itr!=m.end();++itr){ os << '(' << itr->first << ',' << itr->second << ')'; if (++itr!=m.end()) os << ','; --itr; } os << '}'; return os; } template ostream &operator<<(ostream &os,const set &s){ os << '{'; for (auto itr=s.begin();itr!=s.end();++itr){ os << *itr; if (++itr!=s.end()) os << ','; --itr; } os << '}'; return os; } void debug_out(){cerr << '\n';} template void debug_out(Head&& head,Tail&&... tail){ cerr << head; if (sizeof...(Tail)>0) cerr << ", "; debug_out(move(tail)...); } #ifdef LOCAL #define debug(...) cerr << " ";\ cerr << #__VA_ARGS__ << " :[" << __LINE__ << ":" << __FUNCTION__ << "]" << '\n';\ cerr << " ";\ debug_out(__VA_ARGS__) #else #define debug(...) 42 #endif template T gcd(T x,T y){return y!=0?gcd(y,x%y):x;} template T lcm(T x,T y){return x/gcd(x,y)*y;} template inline bool chmin(T1 &a,T2 b){ if (a>b){a=b; return true;} return false; } template inline bool chmax(T1 &a,T2 b){ if (a class modint{ using i64=int64_t; using u32=uint32_t; using u64=uint64_t; public: u32 v; constexpr modint(const i64 x=0) noexcept :v(x<0?mod-1-(-(x+1)%mod):x%mod){} constexpr u32 &value() noexcept {return v;} constexpr const u32 &value() const noexcept {return v;} constexpr modint operator+(const modint &rhs) const noexcept {return modint(*this)+=rhs;} constexpr modint operator-(const modint &rhs) const noexcept {return modint(*this)-=rhs;} constexpr modint operator*(const modint &rhs) const noexcept {return modint(*this)*=rhs;} constexpr modint operator/(const modint &rhs) const noexcept {return modint(*this)/=rhs;} constexpr modint &operator+=(const modint &rhs) noexcept { v+=rhs.v; if (v>=mod) v-=mod; return *this; } constexpr modint &operator-=(const modint &rhs) noexcept { if (v0){ if (exp&1) res*=self; self*=self; exp>>=1; } return res; } constexpr modint &operator++() noexcept {if (++v==mod) v=0; return *this;} constexpr modint &operator--() noexcept {if (v==0) v=mod; return --v,*this;} constexpr modint operator++(int) noexcept {modint t=*this; return ++*this,t;} constexpr modint operator--(int) noexcept {modint t=*this; return --*this,t;} template friend constexpr modint operator+(T x,modint y) noexcept {return modint(x)+y;} template friend constexpr modint operator-(T x,modint y) noexcept {return modint(x)-y;} template friend constexpr modint operator*(T x,modint y) noexcept {return modint(x)*y;} template friend constexpr modint operator/(T x,modint y) noexcept {return modint(x)/y;} constexpr bool operator==(const modint &rhs) const noexcept {return v==rhs.v;} constexpr bool operator!=(const modint &rhs) const noexcept {return v!=rhs.v;} constexpr bool operator!() const noexcept {return !v;} friend istream &operator>>(istream &s,modint &rhs) noexcept { i64 v; rhs=modint{(s>>v,v)}; return s; } friend ostream &operator<<(ostream &s,const modint &rhs) noexcept { return s< struct Trie{ struct TrieNode{ char c; int dep; vector nxt,idxs; TrieNode(char c,int dep):c(c),dep(dep),nxt(char_size,-1){} }; vector Nodes; function ctoi; Trie(function ctoi):ctoi(ctoi){ Nodes.emplace_back('$',0); } inline int &next(int node,int c){ return Nodes[node].nxt[c]; } inline int &next(int node,char c){ return next(node,ctoi(c)); } void add(const string &s,int x=0){ int node=0; for (int i=0;i void query(const string &s,const F &f,int l){ int node=0; for (int i=l;i idxs(int node){return Nodes[node].idxs;} }; template struct AhoCorasick:Trie{ using Trie::Trie; using Trie::next; using Trie::ctoi; const int FAIL=char_size; vector cnt; void build(bool heavy=true){ auto &Nodes=this->Nodes; cnt.resize(Nodes.size()); for (int i=0;i que; for (int i=0;i<=char_size;++i){ if (~next(0,i)){ next(next(0,i),FAIL)=0; que.emplace(next(0,i)); } else next(0,i)=0; } while (!que.empty()){ auto &node=Nodes[que.front()]; int fail=node.nxt[FAIL]; cnt[que.front()]+=cnt[fail]; que.pop(); for (int i=0;i w; set_union(u.begin(),u.end(),v.begin(),v.end(),back_inserter(w)); u=w; } que.emplace(node.nxt[i]); } else node.nxt[i]=Nodes[fail].nxt[i]; } } } map match(const string &s,int now=0){ auto &Nodes=this->Nodes; map res; for (auto c:s){ now=next(now,ctoi(c)); for (auto &id:Nodes[now].idxs) ++res[id]; } return res; } int move(const char &c,int now){ while (next(now,ctoi(c))<0) now=next(now,FAIL); return next(now,ctoi(c)); } pair move(const string &s,int now=0){ long long res=0; for (auto &c:s){ int nxt=move(c,now); res+=cnt[nxt]; now=nxt; } return {res,now}; } int count(int node){return cnt[node];} }; using mint=modint; int main(){ cin.tie(0); ios::sync_with_stdio(false); int N; ll L,R; cin >> N >> L >> R; vector fib(2); fib[0]=fib[1]=1; for (int i=2;fib[i-1]+fib[i-2]<=R;++i){ fib.emplace_back(fib[i-1]+fib[i-2]); } AhoCorasick<10> AHO([](char c){return c-'0';}); for (ll f:fib){ if (L<=f){ AHO.add(to_string(f)); } } AHO.build(false); int n=AHO.size(); vector> dp(N+1,vector(n,0)); dp[0][0]=1; for (int i=0;i