Dice and Candies

Time limit2sMemory limit512 MB

Summary

Find the expected number of throws of a fair six-sided die until the running sum reaches at least N, and print the value to six decimals.

Level: Medium6 of 10
Topics: Dynamic programming, Probability, Math, Implementation
Solved: No attempts yet

Problem

Hyobin has a die with the numbers 1 through 6 written on its faces, one number per face. Each throw gives her as many candies as the number on the top face. Every face comes up with probability $\frac{1}{6}$ .

Hyobin keeps throwing the die until the candies she has received add up to at least $N$ . Write a program that computes the expected number of throws.

Input

The first line contains an integer $N$ ( $1 \le N \le 1{,}000{,}000$ ).

Output

Print the expected number of throws on the first line, rounded to six digits after the decimal point. Always print exactly six digits after the point, padding with zeros. No $N$ puts the exact value on a rounding boundary.

Examples3

Example 1
Input
```
1
```
Expected output
```
1.000000
```
Example 2
Input
```
2
```
Expected output
```
1.166667
```
Example 3
Input
```
7
```
Expected output
```
2.521626
```