Multiplying Digits

Time limit3sMemory limit512 MB

Summary

Given base B and target N, find the smallest positive integer whose base-B digits multiply to N, or report that none exists.

Level: Hard8 of 10
Topics: Number theory, Dynamic programming, Greedy, Math
Solved: No attempts yet

Problem

Multiply together every digit of a positive integer and you get a non-negative integer. In base 10 this rule defines a function $f$ . For example, $f(38) = 3 \times 8 = 24$ .

The same rule works in any base. Written in base 3, the number 80 is 2222, so $f_3(80) = 2 \times 2 \times 2 \times 2 = 16$ .

Solve the reverse problem. Given a base $B$ and a target $N$ , find the smallest positive integer $X$ with $f_B(X) = N$ , where $f_B(X)$ is the product of the digits of $X$ written in base $B$ .

Input

The first line contains two integers $B$ and $N$ separated by a space ( $2 < B \le 10000$ , $0 < N < 2^{63}$ ).

Output

Print, in base 10, the smallest positive integer $X$ with $f_B(X) = N$ . If no such $X$ exists, print impossible instead. Every input for which $X$ exists satisfies $X < 2^{63}$ .

Examples4

Example 1
Input
```
10 24
```
Expected output
```
38
```
Example 2
Input
```
10 11
```
Expected output
```
impossible
```
Example 3
Input
```
9 216
```
Expected output
```
546
```

Example 4

Input

10000 5810859769934419200

Expected output

5989840988999909996