Description

There're $n$ doors on the stage, exactly one car is behind one of the doors. A game with the above setting is played on the stage.

The game has $m$ turns. At the beginning of each turn, player Antimo51 is supposed to choose one of the closing doors without opening it and the host will open some doors other than that door. Specifically, in the $i$-th turn of the game, the host will open $k_i$ doors that are not opened, not chosen, and not in front of the car. Note that a door will not be closed again once it is opened. At the end of each turn, Antimo51 can choose to terminate the game. If so, he can choose a door (which can be the same as one of those chosen in the previous turns) and get the prize behind it. If all $m$ turns are played, Antimo51 must choose a door and get the prize behind it.

The host will try to minimize Antimo51's probability of getting the car. Please find out a strategy for Antimo51 that maximizes that probability. Output the maximum probability that you can get.

Input

The first line contains two integers $n$ and $m$ $(3\le n\le 100,1\le m\le n-2)$, denoting the number of doors and the number of turns.

The second line contains $m$ integers, where the $i$-th integer denotes $k_i$ $(1\le k_i\le n-2)$, the number of the doors to be chosen by the host in the $i$-th turn.

It's guaranteed that $\sum{k_i} \le n-2$.

Output

Output the answer as a minimal fraction.

Specifically, output two integers $a$ and $b$ separated by a space, denoting that the answer equals $\frac ab$. The numbers $a$ and $b$ must satisfy that $\gcd(a,b)=1$ and $a,b>0$, where $\gcd(a,b)$ denotes the greatest common divisor of $a$ and $b$. Note that, when the answer is an integer, although $b=1$, you should still output $b$.

Samples

3 1
1

2 3

4 1
2

3 4

6 2
2 1

5 12

Note

In the first example, Antimo51 should choose the door other than the one chosen at the beginning, resulting in a probability of $\frac 23$.

Resources

电子科技大学第十三届 ACM 趣味程序设计竞赛