eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач

Cube

Лимит времени 0.5 секунд
Лимит использования памяти 256 MiB

There is a cube, which has "1" in its vertices. Let us perform the following operation on it. We will split the cube into 8equal cubes and assign to new vertices numbers equal to the sum of numbers in adjacent vertices. Given that, we will get another cube from the initial one:

Furthermore we can repeat this operation on all received cubes again and again. In this problem we are interested in the sum of all numbers in the cube that we get after we perform the given operation n times.

Входные данные

Input contains single non-negative integer n10^18.

Выходные данные

Print the answer to the question in the statement on a single line modulo 10^9+7.

Пример

Входные данные #1
0
Выходные данные #1
8
Источник ACM-ICPC Ukraine 2012, 2nd Stage Ukraine, September 6, 2012