ll@N;Matrix<mint>M(6,6);M[0][0]=M[0][1]=1;M[1][0]=1;M[2][2]=M[2][3]=1,M[2][4]=2;M[3][2]=1;M[4][2]=M[4][4]=1;M[5][2]=M[5][3]=M[5][5]=1,M[5][4]=2;M=M**(N-1);vector<mint>T{1,0,1,0,0,1};mint ans=0;rep(i,6)ans+=T[i]*M[5][i];wt(ans);