题目描述

给出一颗 $n$ 个结点的树，每个结点上有 N，O，I 三个字母其中一个。

一眼望去，树上有很多 NOI。一个"NOI三元组"定义为：三个分别为 N，O，I 的结点，且 O 结点在 N 结点和 I 结点之间的必经路径上。

你需要计算出 NOI 三元组的个数。由于答案可能很大，对 $10^9+7$ 取模。

输入格式

第一行一个整数 $n$，表示结点个数。结点编号为 $1\ldots n$。

第二行由 $n$ 个大写字母 N 或 O 或 I 组成的字符串，依次表示每个结点上的字母。

接下来 $n-1$ 行，每行两个整数 $u_i,~v_i$，表示树上的一条边，连接 $u_i$ 和 $v_i$ 两个结点。

输出格式

一行一个整数，表示 NOI 三元组的个数。由于答案可能很大，对 $10^9+7$ 取模。

5
ONION
1 2
1 3
1 4
4 5

3

说明

对于 $30\%$ 的数据，$n \le 100$。

对于另外 $30\%$ 的数据，$u_i+1=v_i$。

对于 $100\%$ 的数据，$n\le 10^5$。

本题使用 Subtask。