P1520 Factorization

One day, little W was in math class and heard the teacher explain techniques for factorization, including augmentation-deletion (zēng bǔ shān chú) and the cross multiplication method. He thought they were amazing and wanted to use them to solve problems, but then he ran into a problem he couldn’t solve. Can you help him?

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).

A single line containing a positive integer $n$.

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.

### 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