Path Counting

루트가 있는 트리가 주어진다. 노드 x의 깊이를 d(x)라고 하자. 루트의 깊이는 1이고, 그 외의 임의의 노드 x의 깊이는 d(y) + 1이다. 여기서 y는 x의 부모이다.

이 트리는 다음 성질을 가진다. d(x) = i인 모든 노드 x는 정확히 ai개의 자식을 가진다. 노드가 가질 수 있는 최대 깊이는 n이고, an = 0이다.

트리에서 두 정점을 잇는 단순 경로의 간선 수가 k와 같은 정점의 순서 없는 쌍의 개수를 fk로 정의한다.

모든 1 ≤ k ≤ 2n - 2에 대해 fk를 109 + 7로 나눈 나머지를 계산한다.

입력의 첫 줄에는 정수 n (2 ≤ n ≤ 5 000) — 노드의 최대 깊이가 주어진다.

입력의 둘째 줄에는 n - 1개의 정수 a1, a2, ..., an - 1 (2 ≤ ai ≤ 109)가 주어진다. 여기서 ai는 d(x) = i인 모든 노드 x의 자식 수이다. an = 0이므로 입력으로 주어지지 않는다.

2n - 2개의 수를 출력한다. 이 수들 중 k-th는 fk를 109 + 7로 나눈 나머지와 같아야 한다.

첫 번째 예제의 트리는 다음과 같다.