Pentagon Circle Spanning Trees

A pentagon circle is a special graph constructed as follows. First, there is a central cycle with n vertices and n edges. For each edge of this cycle, a pentagon is attached such that the edge is one side of the pentagon. Specifically, for every edge connecting vertices v_i and v_i+1 (indices taken modulo n), a pentagon is formed by adding three new vertices. Thus, each pentagon has 5 vertices (two of which are shared with the central cycle) and 5 edges. All the pentagons only share vertices on the central cycle.

Your task is to compute the number of different spanning trees of the entire graph (all vertices are considered distinct). Recall that a spanning tree of a graph is a subgraph that connects all the vertices and has exactly (number of vertices - 1) edges without creating any cycle.

After analysis one may show that the answer is given by the formula:

That is, for a given pentagon circle with parameter n, output n * 4^(n-1).

inputFormat

The input consists of a single integer n (1 ≤ n ≤ 10⁵, for example) representing the number of pentagons (which is also the number of vertices in the central cycle).

outputFormat

Output a single integer which is the number of different spanning trees of the given pentagon circle. The answer is given by the formula: $$n\times 4^{n-1}$$.

sample

3

48