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