まずはじめに、条件を満たす \(S\) がどのようなパターンからなるのかを考えてみます。
\(a\) を \(10\) 進表記した文字列を反転させてできる数を \(\mathrm{rev}(a)\) と表すと、次の \(3\) 通りからなることがわかります。

• N
• x*rev(x)
• x*(式)*rev(x)

ここで実は \(2\) 番目のパターンは考慮しなくてよいです。なぜならば、x*rev(x) が問題文の条件を満たす時は x*1*rev(x) もまた問題文の条件を満たすため、\(3\) 番目のパターンで事足りるからです。

よって N と x*(式)*rev(x) の 2 パターンだけを考慮すればよいことがわかりました。
また、細かい事実として次のようなこともわかります。

• \(x = 1\) のケースは考慮しなくてよい。なぜならば、1*(式)*1 が問題文の条件を満たす時は (式) もまた条件を満たすからである。
• \(x \gt \sqrt{N}\) のケースは考慮しなくてよい。なぜならば、\(x \gt \sqrt{N}\) かつ x*(式)*rev(x) が問題文の条件を満たす時は \(\mathrm{rev}(x) \leq \sqrt{N}\) であり rev(x)*(式)*x もまた条件を満たすからである。

この事実を利用すると、関数 \(f\) を

• \(f(n)\) : (\(N = n\) としたときに問題文の条件を満たす文字列が存在すればそれを返し、存在しなければ空文字列を返す関数)

と定義した時、\(f\) 内部で次の一連の処理を行えばよいことがわかります。

• \(n\) が \(0\) を各桁に含まない回文数である場合は n を返す。
• そうでない場合、\(x=2, 3, \dots, \lfloor \sqrt{n} \rfloor\) の順に走査を行い、以下の処理を行う。
  • \(n \bmod{x} = 0\) かつ \(x\) が \(0\) を各桁に含まない場合、以下の処理を行う。
    • \(y = \mathrm{rev}(x)\) とする。
    • \(\frac{n}{x}\bmod{y} = 0\) かつ \(f(\frac{n}{xy})\) が空文字列でない場合は、x* \(f(\frac{n}{xy})\) *y を返り値として return する。
• 空文字列を返り値として return する。

計算量を考えます。上記の内容をそのまま実装すると同じ引数の関数が複数回呼び出されて計算量が評価しづらいですが、\(f\) をメモ化再帰することにすると、\(f(n)\) として呼び出されるものは \(n\) が \(N\) の約数の場合に限られることを利用すれば、かなり大雑把な評価をしても \(\mathrm{O}(\sqrt{N} \times (N の約数の個数))\) 程度で抑えられます。この計算量評価は定数倍が非常に軽いことと、実際は呼び出されない引数が多いことを考えると、この実装で十分に高速に動作することがわかります。(実装によっては \(\mathrm{O}((N の約数の個数)^2)\) 程度で抑えることもできます)

• 実装例 (Python)

import functools
import math


@functools.cache
def f(N):
    if not "0" in str(N) and str(N) == str(N)[::-1]:
        return str(N)
    for x in range(2, math.isqrt(N) + 1):
        if N % x == 0 and not "0" in str(x):
            y = int(str(x)[::-1])
            if N // x % y == 0 and len(f(N // x // y)) != 0:
                return str(x) + "*" + f(N // x // y) + "*" + str(y)
    return ""


N = int(input())
print("-1" if len(f(N)) == 0 else f(N))