숫자 숏코딩

양의 정수 $N$이 주어진다. 0부터 9까지의 숫자와 곱하기 *, 거듭제곱 ^ 연산기호를 이용하여 $N$을 표현하는 가장 짧은 길이의 식을 구하시오.

식은 후위 표기법으로 나타내고, 각 수 또는 연산기호는 공백으로 구분한다. 단, 공백은 식의 길이에 포함하지 않는다.

양의 정수 $N$이 주어진다. $(1 \leq N \leq 10^8)$

$N$을 표현하는 가장 짧은 길이의 식을 후위 표기법으로 출력한다. 가능한 식이 여러 개라면 그중 아무거나 하나를 출력한다.

후위 표기법은 연산자를 연산 대상의 뒤에 쓰는 표기법이다. 식을 앞에서부터 읽으며 수는 스택에 저장하고, 연산자를 만나면 스택에서 두 수를 꺼내 계산한 뒤 결과를 다시 스택에 넣는다.

예를 들어 후위 표기식 3 2 3 * ^는 다음과 같이 $729$로 계산된다.

1. $3$, $2$, $3$이 차례로 스택에 들어간다.
2. 스택에서 $2$, $3$을 꺼내 곱한 값 $2\times 3 = 6$을 스택에 넣는다.
3. 스택에서 $3$, $6$을 꺼내 거듭제곱한 값 $3^6=729$를 스택에 넣는다.