부서 통합

시간 제한1초메모리 제한256 MB

요약

두 부서를 크기의 곱을 비용으로 합쳐 하나로 만들 때 전체 비용과 순서가 있는 합병 과정의 수를 1000000007로 나눈 나머지를 구합니다.

난이도: 보통10점 중 5점
유형: 수학, 조합론
정답자: 아직 제출이 없습니다

문제

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

남은 부서 중에서 부서 a를 하나 고른다.
남은 부서 중에서 a가 아닌 부서 b를 하나 고른다.
부서 a와 부서 b를 합친다. $S_a$ 는 $S_a + S_b$ 가 되고, 부서 b는 사라진다.
합친 부서의 쌍 $(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)$ 은 서로 다른 경우로 센다.

예제3

예제 1
입력
```
2
2 3
```
예상 출력
```
6
2
```
예제 2
입력
```
1
7
```
예상 출력
```
0
1
```
예제 3
입력
```
3
1 2 3
```
예상 출력
```
11
12
```