혼란의 이름으로

여론이라는 것은 존재하지 않는다.

---

조던 엘렌버그, 미국의 수학자

K시에는 서로 연결망을 구축하려는 주민 n명이 살고 있다. 그런데 어떤 주민은 전선을 검은색으로 칠하기를 원하고, 또 어떤 주민은 흰색으로 칠하기를 원한다. 주민 i의 의견은 수 ai로 나타낼 수 있다. 주민 i와 j 사이에 전선을 놓으면 그 전선의 비용은 ai × aj이다.

K시의 시장은 다음 조건을 만족하도록 연결망을 구축하려고 한다.

1. 전선을 정확히 n − 1개 사용한다.
2. 서로 다른 두 주민 i와 j에 대해, p1 = i, pk = j이고 1 ≤ ℓ < k인 모든 ℓ에 대해 주민 pℓ과 pℓ+1이 전선을 공유하는 수열 p1, · · · , pk가 존재한다.

다시 말해, 연결망은 트리여야 한다.

K시의 저명한 수학자인 당신은 연결망을 구축하는 최소 비용만 알고 싶은 것이 아니다. 혼란의 이름으로, 최대 비용도 알고 싶다!

첫째 줄에는 주민의 수를 나타내는 n이 주어진다. 둘째 줄에는 n개의 수 a1, a2, . . . , an이 주어진다. 주민 i의 의견은 ai로 나타낼 수 있다.

한 줄에 공백으로 구분하여 두 수를 출력한다. 첫 번째 수는 연결망을 구축하는 최소 비용이고, 두 번째 수는 최대 비용이다. 비용의 절댓값이 매우 클 수 있으므로 답을 109 + 7로 나눈 나머지를 출력해야 한다. 수의 나머지(도널드 커누스가 정의한)는 a mod b = a − b⌊a/b⌋임에 유의하라. 출력하는 수는 음수가 아니어야 한다.

• 1 ≤ n ≤ 106
• |ai| ≤ 106