Cube#3759
There is a cube, which has in its vertices. Let us perform the following operation on it. We will split the cube into equal 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 times.
Input contains single non-negative integer n \le 10^{18}.
Print the answer to the question in the statement on a single line modulo 10^9+7.
Example 1