Irreducible Factorization of (x^n-1)

Given a positive integer n, factorize the polynomial $$x^n-1$$ into irreducible factors over \(\mathbb{Z}[x]\). It is known that

where \(\Phi_d(x)\) is the d-th cyclotomic polynomial (which is irreducible over \(\mathbb{Z}\)). Your task is to output the factorization in the form of factors enclosed in parentheses and multiplied together. For example, when n = 3, the correct output is:

(x-1)*(x²+x+1)

inputFormat

The input consists of a single integer n (1 ≤ n ≤ 100), representing the exponent in the polynomial \(x^n-1\).

outputFormat

Output a single line containing the irreducible factors of \(x^n-1\) in the format:

(factor1)*(factor2)*...*(factorK)

Each factor should be shown in its standard polynomial form. For instance:

• If n=1, output: x-1
• If n=2, output: (x-1)*(x+1)
• If n=3, output: (x-1)*(x^2+x+1)
• If n=4, output: (x-1)*(x+1)*(x^2+1)

sample

1

x-1