Full Steiner Topologies#3508
Full Steiner topology for a given set of points 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 is the set of edges. The distinctly labeled leaves of , 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 Steiner vertices, are mutually indistinguishable and each has 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 , the cardinality of , compute the number of distinct full Steiner topologies.
The input contains multiple test cases. Each test case consists of a single integer (3 ≤ n ≤ 10^7) 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 \cdot 10^e be the scientific form of the rounded answer, you shall print me, giving all four significant digits of and removing any leading zeroes before .
Beispiel 1