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

Цю операцію можна повторювати на всіх отриманих кубах знову і знову. У цій задачі нас цікавить сума всіх чисел у кубі, який ми отримаємо після виконання даної операції разів.
Вхід містить одне невід'ємне ціле число n \le 10^{18}.
Виведіть відповідь на запитання в умові в одному рядку за модулем 10^9+7.
Приклад 1