ll@(A,B,C,D,E,N);Matrix<mint>M(4,4),v(4,1);rep(i,4)rep(j,4)M[i][j]=i<2?j?j<2?C:j<3?D:E:!i:2i-3==j;rep(i,4)v[i][0]=i?i<2?B:i<3?A:1:A+B;wt((N?(M**(N-1)*v)[0]:v[2])[0]);