{{mint n,b[]={1,1,3,3,4,8},a;rd(n);for(;n-=1;)a=*b+sum(b(4)),b[0..5]=b[1..];wt(*b);}}