Description

Given a positive integer $k$ ($3 \leq k \leq 15$), form an increasing sequence consisting of all powers of $k$ and all sums of finitely many distinct powers of $k$. For example, when $k = 3$, the sequence is:

$1, 3, 4, 9, 10, 12, 13, \ldots$

(This sequence is in fact: $3^0,3^1,3^0+3^1,3^2,3^0+3^2,3^1+3^2,3^0+3^1+3^2,…$.)

Please compute the value of the $N$-th term of this sequence and output it in base $10$ (decimal).

For example, for $k = 3$ and $N = 100$, the correct answer is $981$.

Input Format

Two positive integers $k$ and $N$ separated by a space ($3 \leq k \leq 15$, $10 \leq N \leq 1000$).

Output Format

A single positive integer. Do not print any spaces or other symbols before the integer.

3 100

981

Hint

NOIP 2006 Junior Problem 4.

Translated by ChatGPT 5