Mersenne Composite Numbers

Time limit1sMemory limit128 MB

Summary

Factor every composite Mersenne number 2^P - 1 for prime P up to K and print the factorizations in increasing order.

Level: Medium7 of 10
Topics: Number theory, Math
Solved: No attempts yet

Problem

A Mersenne number is a number of the form $2^P - 1$ , where $P$ is prime.

While $P$ stays small, every Mersenne number looks prime.

Prime $P$	Mersenne number $2^P - 1$
2	$4 - 1 = 3$ , prime
3	$8 - 1 = 7$ , prime
5	$32 - 1 = 31$ , prime
7	$128 - 1 = 127$ , prime

Once $P$ is a large enough prime, however, $2^P - 1$ can fail to be prime. Call a Mersenne number that is not prime a Mersenne composite.

Given an integer $K$ , write a program that finds every Mersenne composite with $P \le K$ and factors it into primes.

Input

The input has a single integer $K$ . ( $K < 63$ )

Output

Print the prime factorization of every Mersenne composite $2^P - 1$ with $P \le K$ , one per line. Each line has this shape.

q1 * q2 * ... * qm = M = ( 2 ^ P ) - 1

Here $M = 2^P - 1$ and $q_1 \le q_2 \le \dots \le q_m$ are the prime factors of $M$ in ascending order. A prime that divides $M$ several times is written that many times. Keep the spacing around the symbols exactly as shown.

Order the lines by the Mersenne composite itself, smallest first. If no such number exists, print nothing.

Examples1

Example 1

Input

Expected output

23 * 89 = 2047 = ( 2 ^ 11 ) - 1
47 * 178481 = 8388607 = ( 2 ^ 23 ) - 1
233 * 1103 * 2089 = 536870911 = ( 2 ^ 29 ) - 1