부서 통합

N개의 부서를 하나로 합치려고 한다. 부서에 1부터 N까지 번호를 붙이고, 부서 i의 크기를 $S_i$라고 하자. 한 번에 여러 부서를 합치면 혼란이 커지므로, 두 부서를 하나로 합치는 작업을 $N - 1$번 반복해서 최종적으로 하나의 부서를 만든다. 한 번의 작업은 다음과 같다.

1. 남은 부서 중에서 부서 a를 하나 고른다.
2. 남은 부서 중에서 a가 아닌 부서 b를 하나 고른다.
3. 부서 a와 부서 b를 합친다. $S_a$는 $S_a + S_b$가 되고, 부서 b는 사라진다.
4. 합친 부서의 쌍 $(a, b)$를 지금까지 기록한 쌍 목록의 맨 뒤에 붙인다.

두 부서를 합치는 데에는 비용이 든다. 합치는 방법에 따라 비용이 다르지만, 비용이 $S_a \times S_b$인 방법을 알고 있으므로 이 방법을 쓴다. 총비용의 최솟값과, 비용이 최소가 되는 서로 다른 과정의 가짓수를 구하여라. 두 과정이 서로 다르다는 것은 기록된 쌍을 순서대로 하나씩 비교했을 때 한 쌍이라도 다르다는 뜻이다.

첫째 줄에 부서의 수 N이 주어진다. ($1 \le N \le 100000$)

둘째 줄에 각 부서의 크기 $S_1, S_2, \dots, S_N$이 공백으로 구분되어 주어진다. 각 크기는 1 이상 100 이하의 자연수이다.

첫째 줄에 총비용의 최솟값을 출력한다.

둘째 줄에 비용이 최소가 되는 서로 다른 과정의 가짓수를 1,000,000,007로 나눈 나머지를 출력한다.

쌍 $(1, 2)$와 쌍 $(2, 1)$은 서로 다른 경우로 센다.