P1062 [NOIP 2006 Junior] Sequence

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$.

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

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

NOIP 2006 Junior Problem 4. Translated by ChatGPT 5