Fibonacci Factorization

Given a positive integer n, compute the n^th Fibonacci number modulo \(2^{31}\) and factorize the result into its prime factors.

The Fibonacci sequence is defined as follows: \(F_1 = 1\), \(F_2 = 1\), and \(F_n = F_{n-1} + F_{n-2}\) for \(n \ge 3\). After computing \(F_n \bmod 2^{31}\), if the result is 0 or 1, output it directly. Otherwise, express the number as a product of its prime factors in increasing order. For a prime factor with exponent 1, simply output the prime; if the exponent is greater than 1, output it in the format \(p^{e}\). Separate factors with a multiplication sign (*) surrounded by spaces.

inputFormat

The input consists of a single integer n indicating the position in the Fibonacci sequence.

outputFormat

Output the prime factorization of \(F_n \bmod 2^{31}\). If the number is 0 or 1, output it directly. Otherwise, for each prime factor output in the format p or p^e (if the exponent is greater than 1), and join factors with * .

sample

3

2