Jackpot

The Great Dodgers company has recently built a brand-new slot machine.

You insert a coin and pull the handle. The machine then picks an integer. If the picked number is $0$, you win the jackpot. Otherwise the machine divides the picked number by each of the lucky numbers $p_1, p_2, \dots, p_n$; if at least one of these divisions leaves remainder $0$, you win.

Great Dodgers want to know the probability of winning. Probability theory does not let us assume that every integer is equally likely, but a mathematician suggested that the winning probability can be approximated by the limit

$\lim_{k \to \infty} \frac{S_k}{2k+1},$

where $S_k$ is the number of integers between $-k$ and $k$ (inclusive) that are divisible by at least one of the lucky numbers. Write a program that computes this probability.

The input contains $n$, the number of lucky numbers ($1 \le n \le 16$), followed by the $n$ lucky numbers $p_1, \dots, p_n$ ($1 \le p_i \le 10^9$). The values may be separated by spaces or newlines.

The requested probability is rational. Output it as an irreducible fraction: print the numerator on the first line and the denominator on the second line. Both must be printed without leading zeroes, and the fraction must be fully reduced.