Олимпиадный тренинг

Задача . H. Подсчет путей

Задача

Задано корневое дерево. Определим d(x) как высоту вершины x: высота корня равна 1, высоты любой другой вершины x равна d(y) + 1, где y — предок вершины x.

У данного дерева есть следующее свойство: каждая вершина x с d(x) = i имеет ровно a_i детей. Максимальная возможная глубина вершины равна n, a_n = 0.

Определим f_k как количество неупорядоченных пар вершин в дереве таких, что количество ребер на простом пути между ними равно k.

Посчитайте f_k по модулю 10⁹ + 7 для всех 1 ≤ k ≤ 2n - 2.

Входные данные

В первой строке записано одно целое число n (2 ≤ n ≤ 5 000) — максимальная глубина вершины.

Во второй строке записаны n - 1 целых чисел a₁, a₂, ..., a_n - 1 (2 ≤ a_i ≤ 10⁹), где a_i — количество детей у каждой вершины x такой, что d(x) = i. Так как a_n = 0, оно не задается во входных данных.