eolymp
bolt
Try our new interface for solving problems
Problems

Full Steiner Topologies

Full Steiner Topologies

Time limit 1 second
Memory limit 64 MiB

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.

Input data

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

Output data

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.

Examples

Input example #1
3
30
300
3000
30000
300000
3000000
Output example #1
1.000E0
8.687E36
5.677E697
1.462E10024
1.983E130306
4.215E1603145
7.937E19031556