仙人掌图（Cactus）是一个连通的无向图，其中每条边最多属于一个简单环。

给定一个包含 $n$ 个顶点和 $m$ 条边的仙人掌图。每个顶点被染成红色、绿色或蓝色。所有顶点按 $1$ 到 $n$ 的顺序编号。此类图的示例如下图所示：

初始时，你位于顶点 $s$。然后你开始移动到某个尚未访问过的相邻顶点，直到不存在这样的顶点为止。选择每个符合条件的顶点的概率是相等的。当不存在这样的顶点时，你停在某个顶点 $t$。如果 $t$ 被染成红色或绿色，则过程停止。如果 $t$ 被染成蓝色，则过程应从顶点 $s$ 重新开始。

你需要编写一个程序，对于给定的仙人掌图，计算过程最终停在红色顶点的概率 $\frac{p}{q}$，并输出整数 $p \cdot q^{-1} \pmod{10^9 + 7}$。其中 $q^{-1}$ 是整数 $q$ 在模 $10^9 + 7$ 下的模逆元。

输入格式

输入的第一行包含三个空格分隔的整数 $n, m$ 和 $s$ ($2 \le n \le 10^5, m \ge n - 1, 1 \le s \le n$)。第二行包含 $n$ 个字符，第 $i$ 个字符表示顶点 $i$ 的颜色：‘R’ 表示红色，‘G’ 表示绿色，‘B’ 表示蓝色。接下来的 $m$ 行，每行包含两个整数 $u_i, v_i$，表示由边连接的顶点编号 ($1 \le u_i, v_i \le n$)。

保证给定的图是一个仙人掌图且不包含重边。

输出格式

输出仅一行，包含一个整数 $p \cdot q^{-1} \pmod{10^9 + 7}$。如果过程是无限的，则输出 “NaN”（不含引号）。

样例

样例输入 1

6 6 1
GRGRGB
1 2
1 3
2 4
3 4
4 5
4 6

样例输出 1

250000002

样例输入 2

14 15 2
RGRGRBGGBRBRGG
1 2
2 3
2 4
5 2
7 4
4 6
10 6
11 7
10 13
11 13
8 5
8 12
8 9
14 9
12 14

样例输出 2

833333340

说明

两个样例均对应题目中的图。第一个样例对应左侧的仙人掌图，第二个样例对应右侧的仙人掌图。