prison

There are an infinite number of prisoners. Initially, the prisoners are numbered 0, 1, 2, ....

Do the following N times:

* Release the 0th prisoner and execute the k, 2k, 3k, ... th prisoners.
* Then renumber the remaining prisoners. At this time, the prisoners with the smallest original numbers are numbered 0, 1, 2, ... in order.



Find the number that was originally assigned to the prisoner released in the Nth operation.

Constraints

* 1 ≤ N ≤ 10 ^ 5
* 2 ≤ k ≤ 10 ^ 5
* The answer is less than 10 ^ {18}.



Input Format

Input is given from standard input in the following format.


N k


Output Format

Print the answer in one line.

Sample Input 1


4 2


Sample Output 1


7


Sample Input 2


13


Sample Output 2


0


Sample Input 3


100000 100000


Sample Output 3


99999






Example

Input

4 2


Output

7

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <string>

using namespace std;

typedef long long ll;

const ll NMAX = ll(10e18) + 1;

int solve();

ll getNextGrad(const ll k, const ll a);

//	戻り値は一回処刑・釈放のプロセスを行った後に
//	targetとなるインデックスの値
ll binarySearch(const ll k, const ll target);

ll jsearch(const ll k, const ll low, const ll high, const ll target);

int main(void) {
	while (solve()) {}
	return 0;
}

/*********

	考察

	N = 4, k = 2の場合

	[1] 0, 1, 2, 3, 4, 5, 6, 7
	[ ] *     *     *     *
	[2] 1, 3, 5, 7, 9, ...
	[ ] *     *     *
	[3] 3, 7, 9, ...
	[ ] *,    *,
	[4] 7 

	一般化して考える
	[1] 0, 1, 2, ..., k, ..., 2k
	[ ] *,  ,  , ..., *, ..., **
		釈放・処刑されるのは
			0, k, 2k, ...

		インデックスの振り直し
		元々のインデックスがiなら
		新しいインデックスは
			i - ( (i / k) + 1 )
			a_[n+1] = a[n] - ( ( a[n]/k ) + 1 )

	[2] 1, 2, 3, ..., k-1, k+1, k+2, ..., 2k-1, 2k+1, 2k+2, 2k+3....
	[ ] 0, 1, 2, ..., k-2, k-1, k  , ..., 2k-3, 2k-2, 2k-1, 2k
		釈放・処刑されるのは
			1, k+2, 2k+3, ...
			->	新たなインデックスは
				
	[3] 2, 3, 4, ...., k-1, k+1, k+3, k+4, ..., 2k-1, 2k+1, 2k+2, 2k+4
	[ ] 0, 1, 2, ...., k-2, k-1, k
		釈放・処刑されるのは
			2, k+3, 

	//	解法：二分探索？

		インデックスi (0 <= i <= 10^18)を二分探索する
		N回目までに処刑されず、かつインデックスが0になればよい

		大小判定は？

		・N回目で生き残り、処刑も釈放もされない -> 大きすぎる
		・N回目までに釈放されてしまう -> 小さすぎる
		・N回目までに処刑される -> ？	：インデックスが大きくなるほどこのパターンが多すぎて二分探索はダメそう

	//	実験してみた
		k = 2のとき
		釈放されるのは
		63:31,15,7,3,1,0,f など
		-> 2の累乗数-1
		
		k = 3のとき

		61:40,26,17,11,7,4,2,1,0,f
		92:61,40,26,17,11,7,4,2,1,0,f
			21,14,9,6,4,3,2,1,1,

		数列が固定化してる -> OEIS案件？

		k = 4のとき
		63:　 47,35,26,19,14,10, (7,5), (3,2,1,0),f
		85:63,47,35,26,19,14,10, (7,5), (3,2,1,0),f
		
		=> kが決まれば釈放されるインデックスの数列は唯一つ決まる
		この数列の(後ろから)n番目が解になる

		ここで逆順に並べておく
		 0,1,2,3,5,6,10,14,19,26,35,47,63,85, X
		ここでXを求めたい

		言い換えれば、以下の式でa[n+1]を求めたい
		a[n]は与えられる
		a[n] = a[n+1] - ( ( a[n+1]/k ) + 1 )

		・単調増加性は担保されるけど、解が一つとは限らない
		-> 解-1,解+1を二分探索で求めてから解一つ一つを吟味すればよい？

		・計算量を考える
			M ;解の範囲の最大値
			二分探索でO( log(M) )
			N回繰り返すから O( N )
			解の吟味は(途中で処刑されるかどうか) O(N)
				->　一回目で処刑されなければ釈放まで生き残ることが保証される
					なぜならa[n]はその作り方から釈放されることが決まっているから
			だからa[n+1]の候補がkで割り切れるかどうかだけ調べておけば十分 -> O(1)

			全体の計算量は O( log(10^18) * 10^5 )で十分間に合いそう

**********/


int solve() {

	ll N, k;
	cin >> N >> k;

	ll next = 1;

	//	コーナーケース
	{
		if (N == 1)
		{
			next = 0;
		}
		else if (N == 2)
		{
			next = 1;
		}
	}
	for (int i = 0; i < N - 2; i++)
	{
		const ll m = binarySearch(k, next - 1);
		const ll M = binarySearch(k, next + 1);
		next = jsearch(k, m, M, next);
	}

	cout << next << endl;


	return 0;
}

ll binarySearch(const ll k, const ll target)
{
	//	[0, NMAX) の範囲に解が存在するはず
	ll low = 0,
		high = NMAX,
		mid = (low+high)/2;

	while (getNextGrad(k,mid) != target)
	{
		mid = (low + high) / 2;

		if (getNextGrad(k, mid) > target)
		{
			high = mid;
		}
		else
		{
			low = mid;
		}

	}

	return mid;
}

ll jsearch(const ll k, const ll low, const ll high, const ll target)
{
	for (ll i = low; i <= high; i++)
	{
		if (getNextGrad(k, i) != target) { continue; }
		if (i % k == 0) { continue; }
		return i;
	}
	return -114514;
}

ll getNextGrad(const ll k, const ll a)
{
	return (a - (a / k + 1));
}

