Prime Check and Factorization

Given a large number N (which might be very big, not necessarily within the range of a 64‐bit signed integer, i.e. (INT64_{MAX} = 9223372036854775807)). Your task is to determine whether N is a prime number and, if it is not, perform its complete prime factorization. Note that problems at this level typically do not have numbers exceeding the int64 range; therefore, if N exceeds (9223372036854775807), you should output Overflow and ignore further processing.

If N is within the range and equal to 1, output Neither followed on the next line by 1 (since 1 is neither prime nor composite).

Otherwise, if N is within range, output two lines: the first line should be Prime if N is a prime number or Composite if it is not; the second line should show the prime factorization of N in ascending order. When writing the factorization, if a prime factor appears more than once, represent it as p^e (with exponent e) and connect different factors with ' * '. For a prime number, simply output the number itself as its factorization.

inputFormat

A single line containing the large integer N as a string. Note that N can be extremely large. For instance, it might exceed the range of int64 ((9223372036854775807)), in which case your program should simply output Overflow.

outputFormat

If N exceeds (9223372036854775807), output a single line with the text Overflow. Otherwise, if N is equal to 1, output two lines: the first line with Neither and the second line with 1. For all other numbers within the range, output two lines: the first line should be either Prime or Composite based on the primality of N, and the second line should list the prime factorization formatted as described (e.g. for 12, output: 2^2 * 3).

sample

12

Composite
2^2 * 3