Young programmer Vasya has a little sister. She likes to play tabletop games, and constantly nags her brother to play with her.
One game she particularly enjoys is played with a dice and a long board. The board is divided into a sequence of N cells. A player starts from the first cell. Each turn, the player throws the dice, obtaining an evenly distributed random number from 1 to 6. The player advances forward by the number of cells equal to the number on the dice. Destination cell is either empty, or contains instruction "jump to the K-th cell". In the latter case, the player immediately moves to the K-th cell instead of the destination cell.
The game ends when the number on the dice is equal to or greater than the number of cells left to the end of the board.
Vasya finds the game rather boring, especially the fact that the instructions on the cells keep sending you back again and again, dragging the game indefinitely.
Vasya wants to calculate the expected value (also known as the mathematical expectation) of the number of moves, so he could estimate the average time required to finish the game.
2 ≤ N ≤ 25, d1 = dN = ddi = 0
There is always at least one sequence of dice throws allowing to finish the game.
|Input file (
|Output file (