Dereck is in chemistry class!

For Dereck's first lab in chemistry, he is told to create a solution. Little does he know, he is actually creating hydrogen cyanide, a deadly (colourless) poison! Unfortunately for him, after creating the solution, he wasn't keeping track of which beaker it was in, and the beaker got mixed with the ~N-1~ other beakers containing distilled water (which is harmless). Now, he must find which beaker contains the poison so that he can properly dispose of it.

Luckily, his teacher, Ms. Zeiler, happened to have a substance that can detect hydrogen cyanide lying around. All he needs to do is to drip one drop of the substance into the beaker with the hydrogen cyanide for it to change colour. Not wanting to contaminate the distilled water beakers with this substance, he will take ~K~ clean cups to use.

In each clean cup, he will pour some amount (possibly none, or infinitesimally small amount) of each beaker's contents into it. Afterwards, he will drip one drop of the substance into each cup to determine if there was hydrogen cyanide. The substance will change colour even if there is only an infinitesimally small amount of hydrogen cyanide in the cup. Afterwards, he will clean the cups completely and repeat the process. This entire process takes exactly ~1~ minute.

Class ends in ~M~ minutes, so Dereck has only ~M~ minutes to determine which beaker contains the hydrogen cyanide! Please determine the minimum value of ~K~ that will be enough for Dereck to complete the task!

Of course, Dereck is smart enough to be able to use the results from the previous minutes in the current minute.

Input Specification

The first line will contain the integer ~N~ ~(1 \le N \le 10^{18})~.
The second line will contain the integer ~M~ ~(1 \le M \le 100)~.

Output Specification

Output the minimum value of ~K~ that allows Dereck to determine which beaker contains the hydrogen cyanide in less than or equal to ~M~ minutes.

It is guaranteed that ~K~ will fit in a 64-bit signed integer.

Constraints

Subtask 1 [35%]

~M = 1, N \le 10^6~

Subtask 2 [65%]

No additional constraints.

Sample Input 1

3
1

Sample Output 1

2

Explanation for Sample 1

One possible way Dereck can use to determine the beaker is:

• We can drip a drop of the contents of beaker ~1~ into cup ~1~.
• We can drip a drop of the contents of beaker ~2~ into cups ~1~ and ~2~.

If only cup ~1~ changes colour, we know beaker ~1~ must have the hydrogen cyanide. If both cups change colour, we know it must be beaker ~2~. Otherwise, it must be beaker ~3~. Thus, we need two cups. We cannot determine which beaker has the hydrogen cyanide with only ~1~ cup.

Sample Input 2

4
1

Sample Output 2

2

Sample Input 3

15
2

Sample Output 3

2

Sample Input 4

10000
2

Sample Output 4

7