Optimized Data Transmission

In computer networks, all data is transmitted in binary form. However, when transmitting large amounts of data, the number of bits required directly using the binary representation can be excessive. For example, to transmit the number \(1024\), one would need 11 bits.

To solve this, an idea is proposed: consider the sequence \(\{a_{n}\}\) defined as all positive integers that can be represented as the sum of distinct powers of a given integer \(k\). In other words, each term in the sequence is the sum of some subset of \(\{k^0, k^1, k^2, \ldots\}\). For instance, when \(k = 3\) the first 7 terms of the sequence are:

\[ 1\;(=3^0),\quad 3\;(=3^1),\quad 4\;(=3^0+3^1),\quad 9\;(=3^2),\quad 10\;(=3^0+3^2),\quad 12\;(=3^1+3^2),\quad 13\;(=3^0+3^1+3^2) \]

If a number \(d\) is the \(p\)-th term of the sequence, then it can be represented by transmitting the two relatively small numbers \(k\) and \(p\). Notice that these two numbers can represent a very large number \(d\) because the sequence corresponds exactly to the numbers whose base \(k\) representation contains only the digits 0 and 1.

Hint: There is a direct correspondence between the binary representation of \(p\) and the value \(d\). In particular, if you express \(p\) in binary and interpret it as a number in base \(k\) (with the least significant bit corresponding to \(k^0\)), you obtain \(d\).

inputFormat

The input consists of a single line containing two positive integers \(k\) and \(p\) (separated by a space), where \(k\) is the base and \(p\) is the index in the sequence.

\(1 \le k \le 10^9\), \(1 \le p \le 10^{12}\) (constraints are indicative).

outputFormat

Output a single integer \(d\), which is the \(p\)-th term of the sequence formed by all sums of distinct powers of \(k\), arranged in increasing order.

sample

3 7

13