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 ~N~-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 ~4^N~ different ~N~-step sequences of notes.

A spin is defined as four consecutive steps that match a cyclic shift of either LDRU or 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 ~N~-step sequences of notes that do not contain any spins.

Input Specification

The first and only line of input will contain a single positive integer ~N~ which will not exceed ~10^{18}~.

Output Specification

Output, on a single line, the number of ~N~-step sequences of notes that do not contain any spins, modulo ~10^9 + 7~.

Sample Data ZIP

Click here for ZIP.

Sample Input

4

Sample Output

248