There is a cube, which has "\textbf{1}" in its vertices. Let us perform the following operation on it. We will split the cube into \textbf{8}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: \includegraphics{https://static.e-olymp.com/content/58/587acc5a3d494ee1139234387cd4fd9101d1c585.jpg} 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 \textbf{n} times. \InputFile Input contains single non-negative integer \textbf{n} ≤ \textbf{10^18}. \OutputFile Print the answer to the question in the statement on a single line modulo \textbf{10^9+7}.