Prime Factorization

Given a positive integer \(M\) (with \(M \ge 2\)), compute its prime factorization. The task is to express \(M\) as a product of prime numbers raised to their respective exponents. For example, if \(M=100\), then \(M = 2^2 \times 5^2\), and the result should be returned in a dictionary format: {2: 2, 5: 2}.

The returned dictionary must have its keys sorted in increasing order. The output format should be exactly as shown: a pair of curly braces containing comma-separated key-value pairs, where each key and its corresponding exponent are separated by a colon. Use the following mathematical relation for prime factorization: \[ M = \prod_{i=1}^{k} p_i^{a_i}, \] where \(p_i\) are prime numbers and \(a_i\) are their powers.

Input/Output: The program reads from standard input and writes the result to standard output.

inputFormat

The input consists of a single integer \(M\) (\(2 \le M \le 10^9\)). This number is given in one line from stdin.

outputFormat

The output is a single line representing the dictionary of prime factors and their exponents. The dictionary should be in the format: {p1: a1, p2: a2, ...} with the prime factors in increasing order. The output should be printed to stdout.

100

{2: 2, 5: 2}