3595：Full Steiner Topologies

A full Steiner topology for a given point set P = {p₁, p₂, …, p_n} is an undirected tree T = (V, E) where V = {v₁, v₂, …, v_n, v_n+1, …, v_2n−2} is the set of vertices, and E is the set of edges. The n distinctly labeled leaves of T, v₁, v₂, …, v_n, correspond to p₁, p₂, …, p_n, respectively; the remaining n − 2 vertices, v_n+1, v_n+2, …, v_2n−2, called the Steiner vertices, are mutually indistinguishable and each have a degree of three. Figure 2 shows the only full Steiner topology for P = {p₁, p₂, p₃}. Figure 3 shows all three different full Steiner topologies for P = {p₁, p₂, p₃, p₄}.

Figure 2: Full Steiner topology for P = {p₁, p₂, p₃}

Figure 3: Full Steiner topologies for P = {p₁, p₂, p₃, p₄}

Given n, the cardinality of P, compute the number of distinct full Steiner topologies.

The input contains multiple test cases. Each test case consists of a single integer n (3 ≤ n ≤ 10⁷) on a separate line. The input ends where EOF is met.

For each test case, print the answer on a separate line. You shall print the answer rounded to four significant digits. Let m · 10^e be the scientific form of the rounded answer, you shall print “mEe”, giving all four significant digits of m and stripping any leading zeroes before e.