Куб

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

Эту операцию можно повторять на всех полученных кубах сколько угодно раз. В данной задаче необходимо найти сумму всех чисел в кубе после выполнения операции n раз.

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

Входные данные содержат одно неотрицательное целое число n ≤ 10^18.

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

Выведите сумму всех чисел в кубе после n операций, взятую по модулю 10^9+7.

Примеры