시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB101513069.767%

문제

정점이 $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$)

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

출력

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

예제 입력 1

5
3 1 4 1 5
1 2
1 3
2 4
2 5

예제 출력 1

17560

주어진 트리는 다음과 같다. 큰 숫자는 정점에 적힌 숫자 $S_i$를, 작은 숫자는 정점의 번호 $i$를 나타낸다.

각 $(a, b)$에 대해 $f(a, b)$는 아래 표와 같다.

1 2 3 4 5
1 $3$ $31$ $34$ $311$ $315$
2 $13$ $1$ $134$ $11$ $15$
3 $43$ $431$ $4$ $4\,311$ $4\,315$
4 $113$ $11$ $1\,134$ $1$ $115$
5 $513$ $51$ $5\,134$ $511$ $5$

따라서, 표 안에 있는 값을 모두 더한 값을 $1\,000\,000\,007$로 나눈 나머지인 $17\,560$을 출력해야 한다.