Prison

Time limit2sMemory limit512 MB

Summary

Simulate a process that repeatedly removes multiples of k from an infinite list of prisoners and renumbers, then report the original label released on step N.

Level: Hard8 of 10
Topics: Math, Combinatorics, Simulation, Number theory
Solved: No attempts yet

Problem

There are infinitely many prisoners. Initially, the prisoners are numbered $0,\ 1,\ 2,\ ...$ .

Perform the following operation $N$ times.

Release prisoner $0$ , and execute prisoners $k,\ 2k,\ 3k,\ ...$ .
Then renumber the remaining prisoners. At this time, number them $0,\ 1,\ 2,\ ...$ in order from the prisoner with the smallest original number.

Find the number originally assigned to the prisoner released in the $N$ -th operation.

Input

The input is given from standard input in the following format.

$N$ $k$

Output

Output the answer on one line.

Constraints

$1\leq N\leq10^5$
$2\leq k\leq10^5$
The answer is at most $10^{18}$ .

Examples3

Example 1
Input
```
4 2
```
Expected output
```
7
```
Example 2
Input
```
1 3
```
Expected output
```
0
```
Example 3
Input
```
100000 100000
```
Expected output
```
99999
```