Problem D
Multiplying Digits
For every positive integer we may obtain a non-negative integer by multiplying its digits. This defines a function $f$, e.g. $f(38) = 24$.
This function gets more interesting if we allow for other bases. In base $3$, the number $80$ is written as $2222$, so: $f_3(80) = 16$.
We want you to solve the reverse problem: given a base $B$ and a number $N$, what is the smallest positive integer $X$ such that $f_ B(X) = N$?
Input
The input consists of a single line containing two integers $B$ and $N$, satisfying $2 < B \leq 10\, 000$ and $0 < N < 2^{63}$.
Output
Output the smallest positive integer solution $X$ of the equation $f_ B(X) = N$. If no such $X$ exists, output the word “impossible”. The input is carefully chosen such that $X < 2^{63}$ holds (if $X$ exists).
| Sample Input 1 | Sample Output 1 |
|---|---|
10 24 |
38 |
| Sample Input 2 | Sample Output 2 |
|---|---|
10 11 |
impossible |
| Sample Input 3 | Sample Output 3 |
|---|---|
9 216 |
546 |
| Sample Input 4 | Sample Output 4 |
|---|---|
10000 5810859769934419200 |
5989840988999909996 |
