{ll@a,@b,@c,@d,@n,x,y,z=-1d12;++n;rep(i,4){x=i&1?b:a;y=i&2?d:c;rep(n&7)x-=y,y+=x+y;z>?=y;}wt(Mint(16)**(n/8)*z);}