Tree Path Concatenation Sum

You are given a tree with n nodes. Each node i contains an integer a_i. For any ordered pair of nodes (x, y), define a path weight w(x,y) as follows:

The path from node x to node y is the unique simple path in the tree. Write down the numbers on the nodes along this path in order. Then, by concatenating these numbers we obtain an integer. For example, if the numbers encountered in order are 3, 21, 0, 5 then the weight is \[ w(x,y)=32105. \]

Your task is to compute the sum of weights of all ordered pairs of nodes, i.e., \[ S=\sum_{x=1}^{n}\sum_{y=1}^{n}w(x,y), \] modulo 998244353.

Note: When concatenating two numbers, if the second number has d digits then concatenation is equivalent to multiplying the first number by \(10^d\) and adding the second number. For a path with nodes \(a_1, a_2, \dots, a_k\) and letting \(d_i\) be the number of digits in \(a_i\), the value is \[ a_1\cdot10^{d_2+d_3+\cdots+d_k}+a_2\cdot10^{d_3+\cdots+d_k}+\cdots+a_{k-1}\cdot10^{d_k}+a_k. \]

inputFormat

The first line contains a single integer n — the number of nodes.

The second line contains n space-separated integers: a1, a2, ..., an.

Each of the next n-1 lines contains two integers u and v (1-indexed) meaning there is an edge between nodes u and v.

outputFormat

Output a single integer: the sum of weights of all ordered pairs of nodes modulo 998244353.

sample

3
1 2 3
1 2
2 3

538