트리 평균 가중치

정점 번호가 $1$부터 $n$까지인 레이블 트리를 생각하자.

트리의 가중치를 모든 간선 $uv$에 대한 $u \cdot \mathrm{sz}\_{uv}(u) + v \cdot \mathrm{sz}\_{vu}(v)$ 값의 합으로 정의하자. 여기서 $\mathrm{sz}\_{vu}(v)$는 간선 $(vu)$를 제거한 뒤 $v$를 포함하는 서브트리의 크기이다.

크기 $n$인 배열 $a$가 주어진다. 배열의 각 원소는 $1$ 이상 $n-1$ 이하의 정수이거나 $-1$이다. $v$번째 원소는 정점 $v$의 차수에 대응된다. 정점 $n$개를 가진 트리가 good하다는 것은, $a\_{v} \ne -1$인 모든 $v$에 대해 $v$의 차수가 $a\_{v}$와 같은 경우를 말한다. 즉, $a\_{v} = -1$이면 $v$는 어떤 차수든 가질 수 있고, 그렇지 않으면 차수가 $a\_{v}$로 고정된다.

good한 트리 중 하나를 균등한 확률로 무작위로 선택하자. 이 트리의 가중치의 기댓값을 $E$라 할 때, $E$의 정수 부분을 구하라.

첫째 줄에 정수 $n$이 주어진다. 이는 트리의 크기이다 ($2 \le n \le 10^{6}$).

둘째 줄에 크기 $n$인 배열이 주어진다. 배열의 각 원소는 $1$ 이상 $n-1$ 이하의 정수(고정된 차수)이거나 $-1$(임의의 차수)이다. 원소의 절댓값의 합이 $2n-2$ 이하임이 보장된다.

$E$의 정수 부분을 출력하라.