Prime Factorization of N!

Given an integer N, compute the prime factorization of N! (that is, the factorial of N) and output the result in the form of a product of terms. For each prime number p such that p ≤ N, the exponent e in N! is given by:

\(e = \sum_{i=1}^{\infty} \left\lfloor \frac{N}{p^i} \right\rfloor\)

The output should be a string of the form:

p₁^e₁*p₂^e₂*...*p_k^e_k

If N is less than 2 (i.e. when N = 0 or 1), output 1 (since 0! and 1! are 1).

inputFormat

The input consists of a single integer N (0 ≤ N ≤ 10⁶ or as defined by the problem constraints).

outputFormat

Output a single line representing the prime factorization of N! in the format:

p₁^e₁*p₂^e₂*...*p_k^e_k

If N is less than 2, output 1.

sample

1

1