namespace IO
{
	const int _Pu=2e7+5,_d=32;
	char buf[_Pu],obuf[_Pu],*p1=buf+_Pu,*p2=buf+_Pu,*p3=obuf,*p4=obuf+_Pu-_d;
	inline void fin()
	{
		memmove(buf,p1,p2-p1);
		int rlen=fread(buf+(p2-p1),1,p1-buf,stdin);
		if(p1-rlen>buf) buf[p2-p1+rlen]=EOF;p1=buf;
	}
	inline void fout(){fwrite(obuf,p3-obuf,1,stdout),p3=obuf;}
	inline LL rd()
	{
		if(p1+_d>p2) fin();LL x=0;
		for(;!isdigit(*p1);++p1);x=(*p1++-'0');
	    for(;isdigit(*p1);++p1) x=x*10+(*p1-'0');
		return x;
	}
	inline void wr(LL x,char end='\n')
	{
		if(!x) return *p3++='0',*p3++=end,void();
		char sta[20],*top=sta;
		do{*top++=(x%10)+'0';x/=10;}while(x);
		do{*p3++=*--top;}while(top!=sta);(*p3++)=end;
	}
}using IO::rd;using IO::wr;

struct jz
{
	LL a[2][2];
	jz(){memset(a,0,sizeof(a));}
	inline void E(){a[0][0]=a[1][1]=1;}
	auto &operator [](int x){return a[x];}
	inline jz operator *(jz y)
	{
		jz z;z[0][0]=((bll)a[0][0]*y[0][0]+(bll)a[0][1]*y[1][0])%mod;z[0][1]=((bll)a[0][0]*y[0][1]+(bll)a[0][1]*y[1][1])%mod;
		z[1][0]=((bll)a[1][0]*y[0][0]+(bll)a[1][1]*y[1][0])%mod;z[1][1]=((bll)a[1][0]*y[0][1]+(bll)a[1][1]*y[1][1])%mod;return z;
	}
}A;