Tudor is learning how to play Dance Dance Revolution!
Tudor is good at stepping to the beat, but is struggling to deal with more complex note patterns. He decides to focus on -step sequences of notes.
There are four different directions that one can step in Dance Dance Revolution - up, down, left, and right. This means there are different -step sequences of notes.
A spin is defined as four consecutive steps that match a cyclic shift of either
LURD. This sequence is called a spin
because in the event that Tudor alternates feet throughout stepping these notes, he will spin around 360 degrees.
Tudor hates spins because they make him dizzy. Compute the number of -step sequences of notes that do not contain any spins.
The first and only line of input will contain a single positive integer which will not exceed .
Output, on a single line, the number of -step sequences of notes that do not contain any spins, modulo .
Sample Data ZIP
Click here for ZIP.