410327: GYM104009 K Restricted Tree

You are given a rooted tree with $$$N$$$ vertices indexed from $$$1$$$ to $$$N$$$ (a connected graph with $$$N$$$ vertices and $$$N - 1$$$ edges), rooted in the vertex $$$1$$$. Each vertex of the tree is assigned a letter from the first $$$10$$$ letters of the English alphabet ($$$"abcdefghij"$$$). Your little sister played with the tree and she deleted the letters from some vertices. Thus, some vertices are empty. As you love palindromes, some vertices from the tree are restricted. If the node $$$i$$$ is restricted, we have the following restriction: there exists a permutation of all the letters contained in the subtree rooted in $$$i$$$, including vertex $$$i$$$, such that the resulting string is a palindrome. Note that a string is palindrome, if it reads the same backward as forward.

As you want to keep all the restrictions true, you need to calculate the number of ways to assign letters to the empty vertices, such that all the restrictions are true. You can assign a letter from the first $$$10$$$ letters of the English alphabet. Because this number can be very large, you need to compute it modulo $$$998244353$$$.

The first line of the input contains the integers $$$N$$$ ($$$1 \leq N \leq 300.000$$$) and $$$Q$$$ ($$$1 \leq Q \leq 5.000$$$).

The following line contains $$$N - 1$$$ numbers, where the $$$i$$$-th number $$$P_i$$$ represents that there is an edge in the tree between vertices $$$P_i$$$ and $$$i + 1$$$, for each $$$1 \leq i \leq N - 1$$$.

The next line contains $$$Q$$$ different numbers between $$$1$$$ and $$$N$$$, representing the vertices that are restricted.

The last line contains a string of length $$$N$$$, consisting only of the first $$$10$$$ letters of the English alphabet and $$$?$$$, representing the value of each vertex. If a vertex has the value equal to $$$?$$$, it means that it is empty.

On a single line, print the number of ways you can assign letters from the first $$$10$$$ letters of the English alphabet to the empty vertices, such that all the restrictions are true. Because this number can be very large, you need to compute it modulo $$$998244353$$$.

5 2
1 1 2 2
1 2
a????

784

12 3
1 1 1 2 2 3 3 5 6 7 7
2 3 7
??a??????a??

95334400