Куб

Є куб, у вершинах якого знаходиться число "1". Виконаємо над ним таку операцію: розділимо куб на 8 рівних кубів і призначимо новим вершинам числа, що дорівнюють сумі чисел у сусідніх вершинах. Таким чином, з початкового куба отримаємо інший:

Цю операцію можна повторювати на всіх отриманих кубах знову і знову. У цій задачі нас цікавить сума всіх чисел у кубі, який ми отримаємо після виконання даної операції n разів.

Вхідні дані

Вхід містить одне невід'ємне ціле число n ≤ 10^18.

Вихідні дані

Виведіть відповідь на запитання в умові в одному рядку за модулем 10^9+7.

Приклади