B. abcde
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a rooted tree with $$$n$$$ nodes, where the root is node $$$1$$$. Each node of the tree is labeled with a lowercase English letter.

You need to count the number of valid 5-tuples of nodes $$$(u_1, u_2, u_3, u_4, u_5)$$$ that satisfy the following conditions. The answer should be computed modulo $$$998244353$$$.

  • $$$u_2$$$ is an ancestor of $$$u_1$$$;
  • $$$u_4$$$ is an ancestor of $$$u_5$$$;
  • $$$u_3$$$ is the lowest common ancestor (LCA) of $$$u_2$$$ and $$$u_4$$$;
  • The letters on nodes $$$u_1, u_2, u_3, u_4, u_5$$$ are 'a', 'b', 'c', 'd', 'e' respectively.
Input

The first line contains a single positive integer $$$n$$$ $$$(1 \leq n \leq 5 \times 10^5)$$$, denoting the number of nodes in the tree. The second line contains a string $$$s$$$ of length $$$n$$$ consisting of lowercase English letters, where $$$s_i$$$ denotes the letter on node $$$i$$$. The third line contains $$$n-1$$$ positive integers $$$fa_2, fa_3, \dots, fa_n$$$, where the $$$i$$$-th integer represents the parent of node $$$(i+1)$$$. It is guaranteed that $$$1 \leq fa_i \lt i$$$.

Output

Print a single integer representing the number of valid 5-tuples modulo $$$998244353$$$.

Examples
Input
5
cbdae
1 1 2 3
Output
1
Input
5
cbdea
1 1 2 3
Output
0
Input
8
ccdbdeae
1 1 2 2 3 4 5
Output
2
Input
9
ccdbdfaee
1 1 2 2 3 4 5 6
Output
2