Double Doors Regional P6 - Tudor Learns More DDR

View as PDF

Submit solution

Points: 17
Time limit: 0.6s
Memory limit: 256M

Problem type

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

Comments

There are no comments at the moment.