小红的树上赋值方案

题目描述

小红拿到了一棵有根树，其中有一些节点被染成了红色。树的根节点是 1 号节点。
小红希望你给每个节点的权值赋值为 1 或者 2，需要满足每个红色节点的子树节点权值之和为 3 的倍数。
请你帮小红求出赋值的合法方案数。由于答案可能过大，请对$10^9+7$取模。

输入格式

第一行输入一个正整数$n$，代表节点的数量。
第二行输入一个长度为$n$的字符串，第$i$个字符为'R'代表$i$号节点被染成红色，为'W'代表未被染色。
第三行输入$n-1$个正整数$a_i$，第$i$个正整数代表$i+1$号节点的父亲编号。
$1\leq n \leq 10^5$

输出格式

一个整数，代表赋值的方案数模$10^9+7$的值。

样例 #1

样例输入 #1

3
RWW
1 1

样例输出 #1

2

提示

有 111 和 222 两种方案