题目：http://codeforces.com/contest/717/problem/A

是 BJOI2019 勘破神机 的弱化版。

令 \( g[i] \) 表示长为 i 、以 1 结尾的方案数，有 \( g[i]=g[i-1]+g[i-2] , g[0]=g[1]=1 \) ；

令 \( f[i] \) 表示长为 i 的方案数，有 \( f[i]=g[i]+g[i-1] \)

发现 \( f[i]=f[i-1]+f[i-2] , f[0]=1 , f[1]=2 \)

那么令 l+=2 , r+=2 ， f[ i ] 就是普通的斐波那契数。用 BJOI 那道题的套路即可。

#include
#include
#include
#define ll long long
using namespace std;
const int N=,mod=1e9+;
int upt(int x){while(x>=mod)x-=mod;while(x<)x+=mod;return x;} int pw(int x,int k) {int ret=;while(k){if(k&)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=;}return ret;}

int k,s[N][N],c[N][N],ans;
int tlen;ll l,r,len;
struct Node{
int x,y;
Node(int x=,int y=):x(x),y(y) {}
Node operator+ (const Node &b)const
{return Node(upt(x+b.x),upt(y+b.y));}
Node operator- (const Node &b)const
{return Node(upt(x-b.x),upt(y-b.y));}
Node operator* (const Node &b)const
{return Node(((ll)x*b.x+(ll)y*b.y%mod*)%mod,((ll)x*b.y+(ll)y*b.x)%mod);}
}A[N],B[N],x1[N],x2[N],one;
Node pw(Node x,ll k)
{Node ret=one;while(k){if(k&)ret=ret*x;x=x*x;k>>=;}return ret;}
void init()
{
s[][]=;
for(int i=;i<=k;i++)
for(int j=;j<=i;j++)
s[i][j]=(s[i-][j-]+(ll)s[i-][j]*(i-))%mod;
for(int i=;i<=k;i++)c[i][]=;
for(int i=;i<=k;i++)
for(int j=;j<=i;j++)
c[i][j]=upt(c[i-][j-]+c[i-][j]);

one=Node(,); int tp=pw(,mod-);
A[]=Node(,tp); B[]=Node(,upt(-tp));
tp=pw(,mod-); x1[]=Node(tp,tp); x2[]=Node(tp,upt(-tp));
A[]=B[]=x1[]=x2[]=one;
for(int i=;i<=k;i++)A[i]=A[i-]*A[];
for(int i=;i<=k;i++)B[i]=B[i-]*B[];
for(int i=;i<=k;i++)x1[i]=x1[i-]*x1[];
for(int i=;i<=k;i++)x2[i]=x2[i-]*x2[];
}
Node Inv(Node x)
{
int tp=upt(((ll)x.x*x.x-(ll)x.y*x.y%mod*)%mod);
tp=pw(tp,mod-);
return Node((ll)x.x*tp%mod,upt(-(ll)x.y*tp%mod));
}
Node cal(Node x)
{
if(x.x==&&x.y==)return Node(tlen,);
return pw(x,l)*(one-pw(x,len))*Inv(one-x);
}
int main()
{
scanf("%d%lld%lld",&k,&l,&r); l+=; r+=;
init(); len=r-l+; tlen=len%mod;
for(int j=,fx=((k&)?upt(-):);j<=k;j++,fx=upt(-fx))
{
int tp=;
for(int t=;t<=j;t++)
{
Node d=cal(x1[t]*x2[j-t]);
d=d*A[t]*B[j-t];
tp=(tp+(ll)c[j][t]*d.x)%mod;
}
ans=(ans+(ll)s[k][j]*fx%mod*tp)%mod;
}
int ml=;
for(int i=;i<=k;i++)ml=(ll)ml*i%mod;
ml=pw(ml,mod-);
ans=(ll)ans*ml%mod;
printf("%d\n",ans);
return ;
}