Uniting Departments

You want to unite N departments into one. Number the departments 1 to N, and let $S_i$ be the size of department i. Merging many departments at once causes too much confusion, so you repeat the operation of merging two departments into one $N - 1$ times until a single department remains. One operation goes like this.

1. Choose one department a among the remaining departments.
2. Choose one department b, different from a, among the remaining departments.
3. Merge department a and department b. $S_a$ becomes $S_a + S_b$, and department b disappears.
4. Append the merged pair $(a, b)$ to the end of the list of pairs recorded so far.

Merging two departments costs something. The cost depends on the method, and you know a method whose cost is $S_a \times S_b$, so you use that one. Find the minimum total cost, and the number of distinct processes whose cost is the minimum. Two processes are distinct when comparing the recorded pairs one by one in order gives at least one differing pair.

The first line contains N, the number of departments. ($1 \le N \le 100000$)

The second line contains N natural numbers $S_1, S_2, \dots, S_N$, the sizes of the departments, separated by spaces. Each size is between 1 and 100.

Print the minimum total cost on the first line.

Print the number of distinct processes whose cost is the minimum, modulo 1,000,000,007, on the second line.

The pair $(1, 2)$ and the pair $(2, 1)$ count as different cases.