Given a full bipartite graph, such that the number of vertices on both sides of the graph is exactly the same. We want to color each edge into three colors: red, blue, or green, such any two red edges do not share the same vertex, while any two blue edges do not share the same. Calculate the number of such colorings! Input A number of test cases (≤ 1000), one per line, each with N (0 ≤ N ≤ 10000000), which is the number of vertices on each side of the graph (a total of 2 ∗ N vertices). Output For each test case, output the answer on one line, modulo 1000000007. Sample Input 1 2 Sample Output 3 35