10913번 - Uniting

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 × S_b인 방법을 알고 있고, 이를 사용할 것이다. 이때 드는 총비용의 최솟값과, 최소한의 비용이 들게 하는 서로 다른 과정의 가짓수를 구해보자. 두 과정이 서로 다르다는 것은, 기록된 쌍들을 순서대로 하나씩 비교했을 때 한 쌍이라도 다르다는 것이다.

첫 번째 줄에 부서의 수를 의미하는 자연수 N (1 ≤ N ≤ 100,000)이 주어진다.

두 번째 줄에는 각 부서의 크기를 의미하는 N개의 자연수 S₁, S₂, ..., S_N이 공백으로 구분되어 주어진다. 이 수들은 1 이상 100 이하이다.

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

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

(1,2)와 (2,1)은 서로 다른 경우이다.