Uniting Batch Compilation commands

$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 100,000$)이 주어진다.

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

출력 형식

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

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

쉬운 문제에서는 첫 번째 줄만 맞으면 정답으로 인정된다.

어려운 문제에서는 두 번째 줄도 맞아야 정답으로 인정된다.

입력

2
2 3

출력

6
2

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