Rainbow Balls

가방에 n가지 서로 다른 색의 공이 들어 있다. i-th번째 색의 공은 ai개 있다.

가방에 서로 다른 색의 공이 적어도 두 개 있는 동안 다음 단계를 수행한다:

• 임의의 공 두 개를 복원 없이 하나씩 꺼낸다. 이 공들은 같은 색일 수도 있다.
• 두 번째 공을 첫 번째 공의 색으로 칠한다. 이 단계에서 공들의 순서를 바꾸는 것은 허용되지 않는다.
• 두 공을 모두 가방에 다시 넣는다.
• 이 모든 행동에는 정확히 일 초가 걸린다.

Let M = 109 + 7이다. 멈출 때까지 필요한 시간의 기댓값은 유리수 로 나타낼 수 있으며, 여기서 P and Q은 서로소인 정수이고 Q는 M으로 나누어떨어지지 않음을 증명할 수 있다. 값 를 반환한다.

입력의 첫 번째 줄에는 색의 수를 나타내는 정수 하나 n (1 ≤ n ≤ 2 500)가 주어진다.

입력의 다음 줄에는 공백으로 구분된 정수 n개, a1, a2, ..., an (1 ≤ ai ≤ 105)이 주어지며, 각각은 각 색의 공의 수를 나타낸다.

문제의 답인 정수 하나를 출력한다.

첫 번째 예제에서는 무슨 일이 일어나더라도 한 단계를 거친 뒤 공들이 같은 색이 된다.

두 번째 예제에는 공이 6개 있다. 공에 1부터 6까지 번호를 붙이고, 일반성을 잃지 않고 공 1,2,3의 초기 색이 1, 공 4,5의 색이 2, 공 6의 색이 3이라고 하자.

다음은 이 단계들이 진행될 수 있는 한 가지 예이다:

• 공 5와 공 6을 선택한다. 그러면 공 6이 색 2가 된다.
• 공 4와 공 5를 선택한다. 공 5는 같은 색(색 2)으로 남는다.
• 공 1과 공 5를 선택한다. 공 5가 색 1이 된다.
• 공 6과 공 5를 선택한다. 공 5가 색 2가 된다.
• 공 3과 공 4를 선택한다. 공 4가 색 1이 된다.
• 공 4와 공 6을 선택한다. 공 6이 색 1이 된다.
• 공 2와 공 5를 선택한다. 공 5가 색 1이 된다.

이 시점에는 모든 공이 같은 색이므로 게임이 끝난다. 이 특정 과정에는 7초가 걸렸다.

이 경우의 답이 임을 보일 수 있다.