Problem D. Distribution by desks ≡
| Author: | Евгений Татаринов, Антон Карабанов | Time limit: | 1 sec | |
| Input file: | Standard input | Memory limit: | 256 Mb | |
| Output file: | Standard output |
Statement
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).
Constraints
1 ≤ n ≤ 1018
Sample tests
| No. | Standard input | Standard output |
|---|---|---|
| 1 | |
|