Description

Factor the polynomial $x^n - 1$ over the ring of integer polynomials (in short, this is a factorization problem), and continue factoring until all factors are irreducible polynomials (i.e., no factor can be further factored).

Input Format

A single line containing a positive integer $n$.

Output Format

Output one line with a single string representing the factorization result.

In the final output, each factor should contain no spaces. Whenever $0$, $1$, the multiplication sign, and parentheses can be omitted, do so whenever possible.

If there are multiple factors, each factor should be written in descending powers, and its leading coefficient must be positive.

In addition, order the factors as follows:

• Prefer factors of lower degree. For factors with the same degree, compare their coefficients term by term from higher to lower exponents (including omitted terms whose coefficients are $0$).
• For coefficients, compare absolute values first, then signs. A smaller absolute value is lexicographically smaller; if absolute values are equal, a negative sign is lexicographically smaller than a positive sign. Factors with lexicographically smaller sequences should be output earlier. See the sample.

12

(x-1)(x+1)(x^2+1)(x^2-x+1)(x^2+x+1)(x^4-x^2+1)

Hint

Hint

$(x^n-1)/(x+1)=\cdots$

Constraints and Conventions

• For $20\%$ of the testdata, $1 \le n \le 200$.
• For $100\%$ of the testdata, $1 \le n \le 5000$.

Translated by ChatGPT 5