Multiplying Digits

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

Hard8Number theoryDynamic programmingGreedyMathNo attempts yetTime limit3sMemory limit512 MB

Description

Examples4

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