Problem C
Pole Colouring

All the street lights of lineland should be coloured red, blue, green, yellow, black or white. Red and blue paint comes in packages that suffice for two poles, and there’s some left over blue paint in storage. Thus an even number of poles must be red and an odd number must be blue. The monochrome paint is also sold in packages that suffice for two poles, so the total number of white and black poles must also be even. In how many ways can the lights be coloured? We consider colouring the first light blue and the second green to be distinct from colouring the first green and the second blue.

Input

The first and only line of input contains a positive integer $n \leq 10^{18}$.

Output

Print the number of ways to print $n$ street lights in a way that satisfies the conditions above. This value might be very large so print it modulo $10^9 + 7$.

8

209920