Куб#3759

Куб

0,5 секунди
256 мегабайтів
Середня

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

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

Вхідні дані

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

Вихідні дані

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

Приклади

Приклад 1

Loading
Loading