给定一棵树，每个节点上都标注有一个来自 ()[]{} 的字符。路径是指一个或多个节点的序列，其中没有重复节点，且每对相邻节点都由一条边连接。如果路径上各节点字符连接而成的字符串是平衡字符串，则称该路径为平衡路径。平衡字符串的定义如下：

• 空字符串是平衡字符串。
• 如果 $s$ 是平衡字符串，则 $(s)$、$[s]$ 和 $\{s\}$ 也是平衡字符串。
• 如果 $a$ 和 $b$ 是平衡字符串，则 $ab$（$a$ 与 $b$ 连接）也是平衡字符串。

计算整棵树中平衡路径的数量。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 5 \cdot 10^3$)。 第二行包含一个长度为 $n$ 的字符串，其中每个字符均为 ()[]{} 中的一个。 接下来的 $n - 1$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u < v \le n$)，表示节点 $u$ 和 $v$ 之间有一条边。保证该图是一棵树。

输出格式

输出一个整数，即整棵树中平衡路径的数量。

样例

样例输入 1

4
()()
1 2
2 3
3 4

样例输出 1

4

样例输入 2

4
[[]]
1 2
2 3
3 4

样例输出 2

2

样例输入 3

6
([]{})
1 2
2 3
3 4
4 5
5 6

样例输出 3

4