Misha 坐下来准备哲学考试。考试将在 $t$ 小时后进行，由 $n$ 个部分组成。在第 $i$ 个部分中，有 $q_i$ 个问题，每个问题需要花费一小时来准备。Misha 在考试中会收到 $n$ 个问题：每个部分会独立且均匀地随机抽取一个问题。为了通过考试，他必须正确回答所有 $n$ 个问题。Misha 可以利用全部 $t$ 小时进行策略性准备，学习问题的一个子集。他能确保通过考试的最大概率是多少？

输入格式

第一行包含两个整数 $t$ 和 $n$：距离考试剩余的时间以及部分的数量（$1 \le t \le 10^9$；$1 \le n \le 10^5$）。下一行包含 $n$ 个整数 $q_1, \dots, q_n$：考试中每个部分的问题数量（$1 \le q_i \le 10^9$）。

输出格式

设 $p = k/\ell$ 为所求概率的最简分数形式。将 $p$ 以模 $M = 10^9 + 7$ 的分数形式输出为两个整数：分子和分母。

形式化地，输出任意两个整数 $x$ 和 $y$（$-2^{63} \le x, y \le 2^{63} - 1$），使得 $x\ell - yk$ 能被 $M$ 整除，且 $y$ 不能被 $M$ 整除。保证这样的数字总是存在。

例如，如果 $0 \le k \le \ell \le 2^{63} - 1$，你可以直接输出 “$k$ $\ell$”。

样例

样例输入 1

1 2
2 2

样例输出 1

0 4

样例输入 2

3 2
2 2

样例输出 2

2 4

说明

如果你更习惯于要求找到有理数模素数的余数 $x$ 的问题，你可以直接输出 “$x$ $1$”，该答案将被接受。特别地，在第二个样例中，答案 “$1$ $2$”、“$-1$ $-2$”、“$1000000006$ $-1000000009$”、“$500000004$ $1$” 以及许多其他答案都将被接受。