Description

众所周知，泥电对大一新生提出了上早自习的要求。作为新生的一员，Ain 很是理解感激学校为了帮助大一新生尽快适应大学生活的良苦用心。但是在 Ain 看来，每天都去同一间自习教室显得有些无趣。因此，Ain 和他的朋友们决定采取一种不同的方式上早自习。

具体的，有 $n$ 间早自习教室，编号从 $1$ 到 $n$。有 $n$ 个大一新生要上早自习，编号也从 $1$ 到 $n$，其中有部分新生是 Ain 和他的朋友们。按学校规定，编号为 $i$ 的新生应该在第 $i$ 间教室上早自习。上早自习时，每个大一新生按编号从小到大的顺序进入教室。

• 对于 Ain 和他的朋友们，他们将会等概率地选择一间无人进入的教室上早自习。
• 对于其他新生，如果他对应的教室无人进入，那么就在这间教室上自习；如果对应的教室已经被占用，那么他会等概率地选择一间无人进入的教室上早自习。

现在 Ain 想知道，在上述策略下，编号为 $n$ 的新生在 $n$ 号教室上早自习的概率是多少？

Input

第一行两个整数 $n$ ($1 \leq n \leq 10^{5}$)，代表新生总人数。

第二行一个长度为 $n$ 的 $01$ 串，表示编号为 $i$ 的新生身份。如果第 $i$ 位为 $1$，表示编号为 $i$ 的新生是 Ain 和他的朋友们；若为 $0$，则为其他新生。

Output

输出一行共两个互质的整数，分别表示所求概率的分子和分母。

若概率为 $0$，输出 $0$ $0$。若概率为 $1$，输出 $1$ $1$。

Samples

3
101

1 2

Note

对于样例，共有三个新生，其中有两个是 Ain 和他的朋友。

如果第 $1$ 个新生选择 $1$ 号教室，则 $3$ 号新生在 $3$ 号教室，概率为 $\frac{1}{3}$。

如果第 $1$ 个新生选择 $2$ 号教室，则 $2$ 号新生的教室被占用。此时如果 $2$ 号新生选择 $1$ 号教室，则 $3$ 号新生在 $3$ 号教室，概率为 $\frac{1}{3}\times \frac{1}{2}=\frac{1}{6}$。如果 $2$ 号新生选择 $3$ 号教室，则 $3$ 号新生无法在 $3$ 号教室上早自习。

如果第 $1$ 个新生选择 $3$ 号教室，则 $3$ 号新生无法在 $3$ 号教室。

综上，答案为 $\frac{1}{3}+\frac{1}{6}=\frac{1}{2}$。

Resources

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