First of all, let us consider what pattern a conforming \(S\) falls into.
Let \(\mathrm{rev}(a)\) denote the number obtained by reversing the decimal representation of \(a\), then it is classified as follows:

• N
• x*rev(x)
• x*(expression)*rev(x)

Here, the second pattern does not actually have to be considered, because if x*rev(x) satisfies the conditions, then so does x*1*rev(x), covered by the third pattern.

Thus, it is sufficient to take the following two patterns into account: N and x*(expression)*rev(x).
Some more trivial observations:

• We do not have to consider \(x = 1\), because if 1*(expression)*1 qualifies, so does (expression).
• We do not have to consider \(x \gt \sqrt{N}\), because if \(x \gt \sqrt{N}\) and x*(expression)*rev(x) satisfies the conditions, then \(\mathrm{rev}(x) \leq \sqrt{N}\), then \(\mathrm{rev}(x) \leq \sqrt{N}\), thus rev(x)*(expression)*x also qualifies.

By this fact, we can define a function \(f\) such that

• \(f(n)\) : (returns a string satisfying the conditions in the problem statement for \(N = n\) if any, and an empty string otherwise)

where \(f\) is internally evaluated as follows:

• Return \(n\) if \(n\) is a palindrome not without a digit \(0\).
• Otherwise, scan \(x=2, 3, \dots, \lfloor \sqrt{n} \rfloor\) in order, as follows:
  • If \(n \bmod{x} = 0\) and \(x\) does not contain a digit \(0\):
    • Let \(y = \mathrm{rev}(x)\).
    • If \(\frac{n}{x}\bmod{y} = 0\), and \(f(\frac{n}{xy})\) is a non-empty string, then return x* \(f(\frac{n}{xy})\) *y.
• Return an empty string.

We now analyze the complexity. If you implement the procedure above naively, the function with the same argument will be called multiple times, which makes it difficult to evaluate the complexity. By adopting memorized recursion, the number of calls is very roughly bounded by about \(\mathrm{O}(\sqrt{N} \times (\text{the number of divisors of }N))\), using the property that \(f(n)\) is called only for divisors \(n\) of \(N\). Since the constant factor is very small, and most arguments are not actually called, this implementation turns out to run fast enough. (Depending on implementation, it can be bounded by about \(\mathrm{O}((\text{the number of divisors of }N)^2)\).

• Sample code (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))