Mint@(A,B,C,D,E,ll N);Matrix<Mint>S(4,4);rep(i,0,3,2)S[i][0]=C,S[i][1]=D,S[i][3]=E;S[1][0]=S[3][3]=S[2][2]=1;if(N<2)wt(B*N+A),exit(0);S=S**--N;wt(S[2][0]*B+S[2][1]*A+S[2][2]*(A+B)+S[2][3]);