В провинции A всего $n$ городов, соединенных $n-1$ дорогой, что образует дерево.
У каждого города $i$ есть неотрицательное целое значение привлекательности $w_i$. Связный подграф $S$, состоящий из городов, называется гармоничным, если среднее значение привлекательности городов в нем равно $1$, то есть $\frac 1{|S|} \sum_{u\in S} w_u = 1$.
Нам неизвестны точные значения привлекательности каждого города; известно лишь, что привлекательность $i$-го города является целым числом, выбранным равномерно случайно из диапазона от $0$ до $a_i$ включительно.
Найдите математическое ожидание количества гармоничных связных подграфов в провинции A. Вам нужно вывести ответ, умноженный на $\prod_{i=1}^n (a_i+1)$. Поскольку ответ может быть очень большим, выведите его по модулю $998244353$.
Входные данные
Первая строка содержит целое положительное число $n$ — количество городов.
Вторая строка содержит $n$ целых положительных чисел, обозначающих $a_i$.
Следующие $n-1$ строк содержат по два целых положительных числа $u, v$, описывающих ребро.
Выходные данные
Выведите одно целое число — ответ на задачу.
Примеры
Пример 1
Входные данные
2 1 2 1 2
Выходные данные
7
Примечание 1
- Если $w_1=1$, то $\{1\}$ гармоничен, вероятность этого события $\frac 12$.
- Если $w_2=1$, то $\{2\}$ гармоничен, вероятность этого события $\frac 13$.
- Если $w_1=w_2=1$ или $w_1=0, w_2=2$, то $\{1, 2\}$ гармоничен, вероятность этого события $\frac 13$.
Таким образом, общее математическое ожидание количества гармоничных связных подграфов равно $\frac 12 + \frac 13 + \frac 13 = \frac 76$. Умножая на $\prod (a_i+1) = 2 \times 3 = 6$, получаем $7$.
Пример 2
Входные данные
3 2 1 3 1 2 1 3
Выходные данные
46
Ограничения
Для $100\%$ данных гарантируется, что $1\le n\le 3000$. Для всех $1\le i\le n$ выполняется $1\le a_i\le n$, а заданные $u, v$ образуют дерево.
Для тестов $1\sim 3$ гарантируется $n\le 50$.
Для тестов $4\sim 5$ гарантируется $\sum a_i \le 5000$.
Для тестов $6\sim 7$ гарантируется, что дерево является цепью, где $v=u+1$.
Для теста $8$ гарантируется $a_i=n$.
Для тестов $9\sim 10$ нет дополнительных ограничений.