22411번 - 監獄 다국어

無限人の囚人たちがいる。はじめ、囚人たちは $0,\ 1,\ 2,\ ...$ と番号が振られている。

次の操作を $N$ 回行う。

• $0$ 番目の囚人を釈放し、$k,\ 2k,\ 3k,\ ...$ 番目の囚人たちを処刑する。
• その後、残った囚人たちに番号を振り直す。このとき、元の番号が小さい囚人から順に $0,\ 1,\ 2,\ ...$ と番号を振る。

$N$ 回目の操作で釈放される囚人がはじめに振られていた番号を求めよ。

入力は以下の形式で標準入力から与えられる。

$N$ $k$

答えを一行に出力せよ。

• $1\leq N\leq10^5$
• $2\leq k\leq10^5$
• 答えは $10^{18}$ 以下である。