给定一个数组 $$$c = [c_1, c_2, \dots, c_m]$$$。数组 $$$a = [a_1, a_2, \dots, a_n]$$$ 的构造方式如下:它由整数 $$$1, 2, \dots, m$$$ 组成,并且对于 [1,m]$$$ 中的每个 $$$i \,在 $$$a$$$ 中恰好出现了 $$$c_i$$$ 整数 $$$i$$$ 。因此,$$$a$$$ 中的元素数量正好是$$$\sum\limits_{i=1}^{m} c_i$$$。
让我们为这样的数组 $$$a$$$ 定义值 $$$f(a)$$$ 为 $$$$$$f(a) = \sum_{\substack{1 \le i < j \le n\\ a_i = a_j}}{j - i}.$$$$$$
换句话说,$$$f(a)$$$ 是所有相等元素对之间的距离总和。
您的任务是计算 $$$f(a)$$$ 的最大可能值以及产生 $$$f(a)$$$ 最大可能值的数组数量。如果某个位置的元素不同,则两个数组被视为不同。
输入
第一行包含一个整数 $$$m$$$ ($$$1 \le m \le 5 \cdot 10^5$$$) — 数组 $$$c$$$ 的大小。
第二行包含 $$$m$$$ 整数 $$$c_1, c_2, \dots, c_m$$$ ($$$1 \le c_i \le 10^6$$$) — 数组 $$$c$$$。
输出
打印两个整数 — $$$f(a)$$$ 的最大可能值以及具有该值的数组 $$$a$$$ 的数量。由于两个答案可能太大,请打印它们对 $$$10^9 + 7$$$ 取模。
示例
输入 #1
6 1 1 1 1 1 1
输出 #1
0 720
输入 #2
1 1000000
输出 #2
499833345 1
输入 #3
7 123 451 234 512 345 123 451
输出 #3
339854850 882811119
注意
在第一个示例中,所有可能的数组 $$$a$$$ 都是 $$$[1, 2, 3, 4, 5, 6]$$$ 的排列。由于每个数组 $$$a$$$ 将具有 $$$f(a) = 0$$$,因此最大值为 $$$f(a) = 0$$$ 并且有 $$$6! = 720$$$ 这样的数组。
在第二个示例中,唯一可能的数组由 $$$10^6$$$ 组成,其 $$$f(a) = \sum\limits_{1 \le i < j \le 10^6}{j - i} = 166\,666\,666\,666\,500\,000$$$ 和$$$166\,666\,666\,666\,500\,000 \bmod{10^9 + 7} = 499\,833\,345$$$。