enum {PR, PT, PL, PB, XR, XT, XL, XB, YR, YT, YL, YB, __};
vector< vector<mint> > M(13, vector<mint>(13));
M[PR][PR] = S; M[PR][YR] = S; M[PR][PT] = L; M[PR][PB] = R;
M[PT][PT] = S; M[PT][XT] = S; M[PT][PL] = L; M[PT][PR] = R;
M[PL][PL] = S; M[PL][YL] =-S; M[PL][PB] = L; M[PL][PT] = R;
M[PB][PB] = S; M[PB][XB] =-S; M[PB][PR] = L; M[PB][PL] = R;
M[XR][XR] = S; M[XR][__] = S; M[XR][XT] = L; M[XR][XB] = R;
M[XT][XT] = S; M[XT][__] = 0; M[XT][XL] = L; M[XT][XR] = R;
M[XL][XL] = S; M[XL][__] =-S; M[XL][XB] = L; M[XL][XT] = R;
M[XB][XB] = S; M[XB][__] = 0; M[XB][XR] = L; M[XB][XL] = R;
M[YR][YR] = S; M[YR][__] = 0; M[YR][YT] = L; M[YR][YB] = R;
M[YT][YT] = S; M[YT][__] = S; M[YT][YL] = L; M[YT][YR] = R;
M[YL][YL] = S; M[YL][__] = 0; M[YL][YB] = L; M[YL][YT] = R;
M[YB][YB] = S; M[YB][__] =-S; M[YB][YR] = L; M[YB][YL] = R;
M[__][__] = S+L+R;
vector<mint> V(13);
V[__] = 1;
return vMul(mPow(M, n), V)[PR].val;
ZW51bSB7UFIsIFBULCBQTCwgUEIsIFhSLCBYVCwgWEwsIFhCLCBZUiwgWVQsIFlMLCBZQiwgX199Owp2ZWN0b3I8IHZlY3RvcjxtaW50PiA+IE0oMTMsIHZlY3RvcjxtaW50PigxMykpOwpNW1BSXVtQUl0gPSBTOyBNW1BSXVtZUl0gPSBTOyBNW1BSXVtQVF0gPSBMOyBNW1BSXVtQQl0gPSBSOwpNW1BUXVtQVF0gPSBTOyBNW1BUXVtYVF0gPSBTOyBNW1BUXVtQTF0gPSBMOyBNW1BUXVtQUl0gPSBSOwpNW1BMXVtQTF0gPSBTOyBNW1BMXVtZTF0gPS1TOyBNW1BMXVtQQl0gPSBMOyBNW1BMXVtQVF0gPSBSOwpNW1BCXVtQQl0gPSBTOyBNW1BCXVtYQl0gPS1TOyBNW1BCXVtQUl0gPSBMOyBNW1BCXVtQTF0gPSBSOwpNW1hSXVtYUl0gPSBTOyBNW1hSXVtfX10gPSBTOyBNW1hSXVtYVF0gPSBMOyBNW1hSXVtYQl0gPSBSOwpNW1hUXVtYVF0gPSBTOyBNW1hUXVtfX10gPSAwOyBNW1hUXVtYTF0gPSBMOyBNW1hUXVtYUl0gPSBSOwpNW1hMXVtYTF0gPSBTOyBNW1hMXVtfX10gPS1TOyBNW1hMXVtYQl0gPSBMOyBNW1hMXVtYVF0gPSBSOwpNW1hCXVtYQl0gPSBTOyBNW1hCXVtfX10gPSAwOyBNW1hCXVtYUl0gPSBMOyBNW1hCXVtYTF0gPSBSOwpNW1lSXVtZUl0gPSBTOyBNW1lSXVtfX10gPSAwOyBNW1lSXVtZVF0gPSBMOyBNW1lSXVtZQl0gPSBSOwpNW1lUXVtZVF0gPSBTOyBNW1lUXVtfX10gPSBTOyBNW1lUXVtZTF0gPSBMOyBNW1lUXVtZUl0gPSBSOwpNW1lMXVtZTF0gPSBTOyBNW1lMXVtfX10gPSAwOyBNW1lMXVtZQl0gPSBMOyBNW1lMXVtZVF0gPSBSOwpNW1lCXVtZQl0gPSBTOyBNW1lCXVtfX10gPS1TOyBNW1lCXVtZUl0gPSBMOyBNW1lCXVtZTF0gPSBSOwpNW19fXVtfX10gPSBTK0wrUjsKdmVjdG9yPG1pbnQ+IFYoMTMpOwpWW19fXSA9IDE7CnJldHVybiB2TXVsKG1Qb3coTSwgbiksIFYpW1BSXS52YWw7Cg==