int tbl[]={
0,1,0,
908460138 , 945351196 , 964927951 ,
371975563 , 80688602 , 946533617 ,
967988087 , 800447448 , 509786860 ,
392460984 , 947746097 , 207105907 ,
864787550 , 220121405 , 200000007 ,
4660654 , 539612979 , 371423623 ,
393241336 , 850278613 , 407794103 ,
530142919 , 975243705 , 885945115 ,
662356693 , 442753488 , 73070046 ,
21 , 999999994 , 999999734 ,
964730508 , 788097308 , 978161894 ,
47291577 , 762534955 , 287143675 ,
897801569 , 921932940 , 250793022 ,
558994539 , 920981438 , 758601952 ,
219772980 , 298960180 , 200012817 ,
173410246 , 82905056 , 54967674 ,
485645421 , 204446108 , 496453263 ,
455258545 , 454833148 , 726782935 ,
777695784 , 153695153 , 672638455 ,
999999020 , 610 , 999397937 ,
749206315 , 14075594 , 838357449 ,
405320339 , 80168765 , 779553125 ,
};

ll n;
mint a,b,s;
{
	rd(n);
	n%=1d9+8;
	a=tbl[n/1d8*3+0];
	b=tbl[n/1d8*3+1];
	s=tbl[n/1d8*3+2];
	n%=1d8;
	rep(n){
		b+=a;
		a=b-a;
		s+=a*a;
	}
	wt(s);
}