题目描述

给定一棵有 $n$ 个顶点的树，顶点编号为 $0,1,\ldots,n-1$。每条边上标有一个小写英文字母。

对于任意有序顶点对 $(x,y)$，沿从 $x$ 到 $y$ 的唯一简单路径依次写下经过边的字符，得到字符串 $L(x,y)$。

如果存在一对顶点 $(x,y)$ 使得 $L(x,y)=S$，则称这棵树包含字符串 $S$。

现给定模式串 pat。保证 pat 中任意两个相邻字符都不同。

你需要选择原树的一个非空连通子图作为子树。两个子树只要顶点集合不同，就视为不同方案。要求选择的子树不包含字符串 pat。

求合法子树数量，对 $10^9+7$ 取模。

输入格式

第一行输入整数 $n$。

第二行输入 $n-1$ 个整数 $p_1,p_2,\ldots,p_{n-1}$。对于 $1\le i<n$，顶点 $i$ 与顶点 $p_i$ 之间有一条边。

第三行输入一个长度为 $n-1$ 的字符串 ch，其中 ch[i-1] 是边 $(i,p_i)$ 上的字符。

第四行输入模式串 pat。

输出格式

输出合法子树数量对 $10^9+7$ 取模的结果。

数据范围

• $2\le n\le 101$；
• 对于 $1\le i<n$，$0\le p_i<i$；
• ch 长度为 $n-1$，只包含小写字母；
• $1\le |pat|\le 8$；
• pat 中没有两个相邻字符相同。

样例

输入

4
0 0 0
aab
ab

输出

8