Expected Cost for Collecting All Stamps

Pippi wants to collect all n different types of stamps. The only way Pippi can acquire a stamp is by purchasing one from FanFan. Every time he buys a stamp, the type is chosen uniformly at random among the n types (each with probability \(1/n\)). However, since FanFan is also a stamp collector, the cost increases with each purchase. Specifically, the first stamp costs 1 unit, the second costs 2 units, the third costs 3 units, and so on, so that the \(k\)-th purchase costs \(k\) units.

Let \(T\) be the total number of purchases needed to collect all \(n\) types. The total cost will then be \[ C = \sum_{k=1}^{T} k = \frac{T(T+1)}{2}. \]

Your task is to compute the expected total cost \(E[C]\) that Pippi will spend in order to collect all \(n\) stamps.

Hint: Recall that in the classic coupon collector problem, the expected number of purchases is \(E[T] = n\,H_n\) where \(H_n = \sum_{i=1}^{n}\frac{1}{i}\) is the \(n\)th harmonic number. Note that computing \(E[T(T+1)]\) requires calculating both \(E[T]\) and \( E[T^2]\). You can obtain \(E[T^2]\) by using the fact that \(T = \sum_{k=1}^n X_k\) where \(X_k\) is the number of purchases needed to obtain the \(k\)-th new stamp, and by using properties of the geometric distribution.

It can be shown (derivation omitted) that the expected total cost can be computed by the formula \[ E[C] = \frac{\left(n\,H_n\right)^2 + n\,H_n + n\sum_{i=1}^{n} \frac{n-i}{i^2}}{2}. \]

inputFormat

The input consists of a single integer n representing the number of different stamps.\(1 \le n \le 10^5\) (for instance).

outputFormat

Output a single floating point number representing the expected total cost. Your answer will be accepted if its absolute or relative error does not exceed \(10^{-6}\).

sample

1

1.0000000000