A full Steiner topology for a given point set P = {p_1, p_2, …, p_n} is an undirected tree T = (V, E) where V = {v_1, v_2, …, 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_1, v_2, …, v_n, correspond to p_1, p_2, …, 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 1 shows the only full Steiner topology for P = {p_1, p_2, p_3}. Figure 2 shows all three different full Steiner topologies for P = {p_1, p_2, p_3, p_4}.
Figure 1: Full Steiner topology for P = {p_1, p_2, p_3}
Figure 2: Full Steiner topologies for P = {p_1, p_2, p_3, p_4}
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^7) on a separate line. The input ends where EOF is met.
E
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 "me", giving all four significant digits of m and stripping any leading zeroes before e.