Problem Description

Score: $ 500 $ points

RZK is in financial trouble. One day, he found a game where you can earn money as follows:

• There is an n-sided die that rolls each number from $ 1 $ to $ n $ with equal probability.
• The player can continue rolling the die until a face that has been rolled before appears. When the player rolls a face with the number $ a $, they earn $ a $ yen. However, if a previously rolled face is rolled again, no money is earned.
• For example, if the player rolls the faces in the order $ 1 $ -> $ 5 $ -> $ 3 $ -> $ 5 $, the player earns $ 1 + 5 + 3 = 9 $ yen.

RZK found the game very appealing, but the entry fee is very high. Therefore, he decided to calculate the expected value of the money earned from the game before considering participation.

Calculate the expected value of the money earned in this game.

Input Format

The input is given from the standard input in the following format:

$ n $

Output Format

Output the expected value of the money earned in this game. The answer will be considered correct if the absolute or relative error is less than $ 10^{-7} $.

Sample Input and Output

Sample Input #1

2

Sample Output #1

2.25000000000000

Sample Input #2

6

Sample Output #2

9.71141975308642

Notes/Hints

Constraints

• $ n $ is an integer between $ 1 $ and $ 500,000 $ inclusive.

Subtasks

Subtask 1 \[ $ 60 $ points \]

• $n \leq 8$.

Subtask 2 \[ $ 120 $ points \]

• $n \leq 18$.

Subtask 3 \[ $ 320 $ points \]

• No additional constraints.

见题面 Input 部分

见题面 Output 部分