All Andrews in general like to play different games. This Andrew is not an exception and he likes to do it as well. Recently, he has attended a casino under some unknown circumstances. Croupier has offered him to play some very attractive game.

You are given a dice with k faces. Each of them has a unique number from 1 to k. You are allowed to roll a dice no more n times and stop after some arbitrary chosen round. The amount of money you win is equals to the last number appeared on the dice top face. All of the outcomes after rolling a dice have equal probabilities of appearance.

Andrew is a quite strong mathematician and hence knows the optimal strategy to maximize the award. Your task is to compute the expected value of the award if you are playing like Andrew, i.e. following the optimal strategy.