Problem D. Distribution by desks

Author:Евгений Татаринов, Антон Карабанов   Time limit:1 sec
Input file:Standard input   Memory limit:256 Mb
Output file:Standard output  


To conduct a mathematics Olympiad for grades 8 − 11, several classrooms have been allocated. The first classroom contains n rows of desks, with each row having 3 desks. Each desk accommodates exactly one person.

The organizers aim to seat students at all desks in the first classroom in such a way that in any 2 × 2 square of desks, students from different grades sit pairwise (meaning, in any square, there is one student from each of the 8th, 9th, 10th, and 11th grades).

In the illustration, you can see one of the suitable seating arrangements for n = 2 (in both the red and green squares, students from different grades are seated).

How many different ways exist to arrange the participants, given that the total number of students in any grade is greater than the number of desks in the first classroom?

Input format

The only input line contains a natural number n.

Output format

Output a single natural number — the answer to the problem's question modulo 109 + 7 (since the number can be very large).


1 ≤ n ≤ 1018

Sample tests

No. Standard input Standard output

0.068s 0.010s 15