Anna 正在为她的 Web 应用程序准备一个新数据库，其中每个数据表行都会分配一个全局唯一标识符（GUID）。厌倦了传统的随机 GUID 生成方法，Anna 决定这次尝试一些新方法。

Anna 找到了一棵拥有 $n$ 个节点的树，其中任意两个节点之间都存在唯一的一条简单路径（简单路径最多访问每个节点一次）。她为每个节点分配了一个十六进制字符（0-9 或 a-f）。为了生成一个 GUID，她选择两个节点 $s$ 和 $t$（不一定不同），并通过将从 $s$ 到 $t$ 的简单路径上的所有十六进制字符拼接起来，构建一个字符串。得到的这个十六进制字符串随后被用作 GUID。请注意，通过这种方法生成的 GUID 没有固定的长度。此外，由 $s$ 到 $t$ 的路径生成的 GUID 可能与由 $t$ 到 $s$ 的路径生成的 GUID 不同。

Anna 可以通过选择不同的节点 $s$ 和 $t$ 来生成不同的 GUID。为了确保她的 GUID 生成方法的质量，她想知道从给定的树中可以生成多少个不同的唯一 GUID。

输入格式

输入的第一行包含一个整数 $n$（$2 \le n \le 2\,000$），表示树中的节点数。节点编号为 $1$ 到 $n$。

接下一行包含一个由 $n$ 个十六进制字符（0-9 或 a-f）组成的字符串，其中第 $i$ 个字符是分配给节点 $i$ 的十六进制字符。

接下来的 $n - 1$ 行每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，$u \ne v$），表示节点 $u$ 和 $v$ 之间存在一条边。保证给定的边构成一棵树。

输出格式

输出一个整数，表示可以从给定的树中生成的唯一 GUID 的数量。

图 D.1：第一个样例的示意图。节点编号标记在每个节点的左上方，十六进制字符显示在中心。

样例

输入样例 1

4
abab
1 2
3 2
2 4

输出样例 1

8

输入样例 2

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

输出样例 2

18

说明

样例 1 说明

从节点 1 或节点 3 出发，你可以获得 4 个唯一的 GUID：a、ab、aba 和 abb。从节点 2 出发，你可以获得 3 个唯一的 GUID：b、ba 和 bb。从节点 4 出发，你可以获得 3 个唯一的 GUID：b、bb 和 bba。总共可以获得 8 个唯一的 GUID。