시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 43 6 5 22.727%

문제

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: f3(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 fB(X) = N?

입력

The input consists of a single line containing two integers B and N, satisfying 2 < B ≤ 10 000 and 0 < N < 263.

출력

Output the smallest positive integer solution X of the equation fB(X) = N. If no such X exists, output the word “impossible”. The input is carefully chosen such that X < 263 holds (if X exists).

예제 입력

10 24

예제 출력

38

예제 입력 2

10 11

예제 출력 2

impossible

예제 입력 3

9 216

예제 출력 3

546

예제 입력 4

10000 5810859769934419200

예제 출력 4

5989840988999909996

힌트