트리 읽기

정점이 $V$개인 트리가 주어진다. 정점에는 $1$번부터 $V$번까지 번호가 붙어 있다. $i$번 정점에는 $1$부터 $9$까지의 숫자 중 하나인 $S_i$가 적혀 있다.

트리의 $a$번 정점과 $b$번 정점에 대해, $a$번 정점에서 $b$번 정점까지의 최단 경로에 포함된 정점들의 숫자를 경로 순서대로 이어 붙인 10진법 정수를 $f(a, b)$라고 하자. 예를 들어 $1$, $2$, $3$번 정점에 적힌 수가 각각 $3$, $4$, $1$이고, $1$번 정점에서 $2$번 정점으로 가는 최단 경로가 $1 \rightarrow 3 \rightarrow 2$이면, $f(1, 2) = 314$이다.

가능한 모든 정수 쌍 $(a, b)$ ($1 \le a, b \le V$)에 대해 $f(a, b)$를 모두 더한 값을 $1\,000\,000\,007$로 나눈 나머지를 구하라.

첫 번째 줄에 $V$가 주어진다. ($1 \le V \le 200\,000$)

두 번째 줄에 $S_1, \cdots, S_V$가 공백으로 구분되어 주어진다. ($1 \le S_i \le 9$)

세 번째 줄부터 $V-1$개의 줄에 걸쳐 트리의 각 간선이 잇는 두 정점의 번호 $x$, $y$가 공백으로 구분되어 주어진다. ($1 \le x, y \le V$)

입력으로 주어지는 모든 수는 정수이다.

첫 번째 줄에 답을 출력한다.