Expected Number of Good Pairs in a Randomly Weighted Complete Graph

You are given a complete graph on n vertices — every pair of distinct vertices is connected by exactly one edge, so there are n * (n - 1) / 2 edges in total. Each edge is independently assigned a weight drawn from the same continuous probability distribution. Because the distribution is continuous, all edge weights are distinct with probability 1.

For a vertex a, define its favorite neighbor as the vertex connected to a by the maximum-weight edge among all n - 1 edges incident to a (with probability 1 this vertex is unique).

An unordered pair of vertices (a, b) is called a good pair if b is the favorite neighbor of a and a is the favorite neighbor of b — that is, the edge between a and b has the maximum weight among all edges incident to a, and also the maximum weight among all edges incident to b.

Given the integer n, return the expected number of good pairs in the graph.

Input

• A single integer n — the number of vertices in the complete graph.

Output

• A single floating-point number: the expected number of good pairs. Answers within an absolute or relative error of 1e-6 of the correct value are accepted.

Constraints

• 2 <= n <= 10^9
• The answer is the same for every continuous distribution, as long as all edge weights are drawn i.i.d. from it — your result must not depend on the particular distribution.
• Your solution must run in O(1) (or at most O(log n)) time. Monte Carlo simulation is neither precise enough nor fast enough at this scale.

Examples

Example 1

Input: n = 2
Output: 1.0

Explanation: The graph has a single edge. Each vertex's only neighbor — and therefore its favorite neighbor — is the other vertex, so the unique pair is always a good pair.

Example 2

Input: n = 4
Output: 1.2