Problem D
GUID Generator

Anna is preparing a new database for her web application, in which a Globally Unique Identifier (GUID) is assigned to each table row. Getting tired of the traditional random GUID generation method, Anna decides to try something new this time.

Anna finds a tree with $n$ nodes, where between each pair of nodes there exists one unique simple path (A simple path visits each node at most once). She assigns each node one hexadecimal character (0-9 or a-f). To generate a GUID, she selects two nodes $s$ and $t$ (not necessarily distinct), and constructs a string by concatenating all the hexadecimal characters along the simple path from $s$ to $t$. This resulting hexadecimal string is then used as a GUID. Note that the GUIDs generated by this method do not have a fixed length. Besides, the GUID produced by the path from $s$ to $t$ may not be the same as the GUID produced by the path from $t$ to $s$.

Anna can generate different GUIDs by choosing different nodes $s$ and $t$. To ensure the quality of her GUID generation method, she wants to know how many unique GUIDs can be generated from the given tree.

Input

The first line of input has a single integer $n$ ($2 \leq n \leq 2\, 000$), the number of nodes in the tree. The nodes are numbered from $1$ to $n$. The next line contains a string of $n$ hexadecimal characters (0-9 or a-f), where the $i$th character is the hexadecimal character assigned to node $i$.

The following $n-1$ lines each contain two integers $u$ and $v$ ($1 \leq u, v \leq n$, $u \neq v$), indicating that there is an edge between nodes $u$ and $v$. It is guaranteed that the given edges form a tree.

Output

Output a single integer, the number of unique GUIDs that can be generated from the given tree.

Explanation of Sample Case 1

Starting from node $1$ or node $3$, you can obtain $4$ unique GUIDs: a, ab, aba, and abb. Starting from node $2$, you can obtain $3$ unique GUIDs: b, ba, and bb. Starting from node $4$, you can obtain $3$ unique GUIDs: b, bb, and bba. In total, there are $8$ unique GUIDs that can be obtained.

Figure 1: Illustration of the first sample case. The node numbers are marked at the top-left of each node, and the hexadecimal characters are shown in the center.

4
abab
1 2
3 2
2 4

8

6
01aa10
1 2
2 3
2 4
4 5
5 6

18