wzj has invented a brand new Ludo game! This game comes with a huge board and a giant die.

wzj really enjoys this game, but he can never gather enough players to start a match. Other people think one full game takes far too much time, so no one wants to play with him.

He wants to prove that the game can end quickly if everyone plays with the optimal strategy. Unfortunately, he does not know how to calculate the exact number of turns.

Could you help him solve this problem?

The board has $$$n$$$ cells numbered from $$$1$$$ to $$$n$$$. Initially, wzj's piece is placed on cell $$$1$$$. There is an $$$m$$$-sided die. Each roll generates an integer chosen uniformly at random from $$$1$$$ to $$$m$$$.

In each turn, wzj first rolls the die. Let the result be $$$x$$$. After seeing $$$x$$$, he has two choices: move forward by $$$x$$$ steps, or skip the turn and stay in place.

• If he chooses to stay, the position of the piece remains unchanged.
• If he chooses to move $$$x$$$ steps. Suppose the current cell is $$$p$$$:
  • If $$$p + x \le n$$$, the piece moves to cell $$$p+x$$$.
  • If $$$p + x \gt n$$$, the piece will bounce back and land on cell $$$n - (p + x - n) = 2n - p - x$$$.

The goal is to reach cell $$$n$$$ as quickly as possible.

Under the optimal strategy (which minimizes the expected number of turns to reach cell $$$n$$$), calculate the expected number of turns needed for wzj to travel from cell $$$1$$$ to cell $$$n$$$.