시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 16 9 8 53.333%

문제

N개의 부서를 하나의 부서로 합치고자 한다. 이 부서들에 1에서 N까지의 번호를 붙이고, 부서 i의 크기를 Si라고 하도록 하자. 한 번에 많은 부서를 합치면 혼란이 커질 것이라고 예상되었기 때문에, 두 개의 부서를 하나로 합치는 것을 N - 1번 반복하여 통합된 하나의 부서를 만들기로 하였다. 반복하는 과정은 아래와 같다.

  1. 남은 부서들 중에 하나의 부서 a를 정한다.
  2. 남은 부서들 중에 a가 아닌 하나의 부서 b를 정한다.
  3. 두 부서 a와 b를 합친다. Sa는 Sa + Sb가 되며, 부서 b는 사라진다.
  4. 합친 부서의 쌍 (a, b)를 현재까지 기록된 합친 부서 쌍의 목록의 가장 뒤에 붙인다.

두 부서를 합치는 데에는 비용이 발생한다. 이때 합치는 방법에 따라 드는 비용이 다르지만 우리는 비용이 Sa × Sb인 방법을 알고 있고, 이를 사용할 것이다. 이때 드는 총비용의 최솟값과, 최소한의 비용이 들게 하는 서로 다른 과정의 가짓수를 구해보자. 두 과정이 서로 다르다는 것은, 기록된 쌍들을 순서대로 하나씩 비교했을 때 한 쌍이라도 다르다는 것이다.

입력

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

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

출력

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

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

예제 입력

2
2 3

예제 출력

6
2

힌트

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

출처

Contest > kriiicon > 제 2회 kriiICPC U번