Description

There is an eternal tree with $n$ nodes. Each node $x(1 \le x \le n)$ has an eternal string $S(x)$.

But there is no eternity in this world. Everything will disappear with time. We can only define an “eternity value” $f$ for each so-called eternal thing. This value itself has no real meaning; it is just a symbol.

• The eternity value $f(S)$ of a string $S$ is defined as its length $\mathrm{Len}(S)$, i.e.:

$$f(S) = \mathrm{Len}(S)$$

• An undirected path in the tree $K = [u, v](u < v)$ means the simple path between $u$ and $v$ (including $u$ and $v$). Its eternity value $f(K)$ is defined as the sum, over all distinct unordered pairs of nodes $(x, y)(x \in K, y \in K, x < y)$ on the path, of the eternity value $f(\mathrm{LCP}(S(x), S(y)))$ of the longest common prefix $\mathrm{LCP}(S(x), S(y))$ of the strings $S(x)$ and $S(y)$, i.e.:

$$f(K) = \sum_{x \in K, y \in K, x < y} f(\mathrm{LCP}(S(x), S(y)))$$

• The eternity value $f(T)$ of a tree $T$ is defined as the sum of the eternity values of all undirected paths $[u, v](u \in T, v \in T, u < v)$ in the tree, i.e.:

$$f(T) = \sum_{u \in T, v \in T, u < v} f([u,v])$$

In particular, the string on each node of the tree comes from an eternal Trie rooted at node $1$. That is, each node in the tree corresponds to a node in the Trie, and the string on that node is the string formed along the path from the Trie root to its corresponding node.

You need to compute the eternity value of this tree. Take the answer modulo $998244353$.

Input Format

The first line contains two positive integers $n, m$, denoting the number of nodes in the tree and the number of nodes in the Trie, respectively.

The second line contains $n$ non-negative integers. The $i$-th number is $a_i$, meaning that the parent of node $i$ in the tree is $a_i$. For the root node $root$, it is guaranteed that $a_{root} = 0$.

The third line contains $m$ non-negative integers. The $i$-th number is $b_i$, meaning that the parent of node $i$ in the Trie is $b_i$. It is guaranteed that $b_i < i$ and $b_1 = 0$.

The fourth line is a string of $m$ characters. The $i$-th character $c_i$ represents the character on the edge between Trie node $i$ and its parent node $b_i$. It is guaranteed that $c_1=\texttt{0}$ and $c_i(2 \le i \le m)\in[\texttt{a},\texttt{z}]$.

The fifth line contains $n$ positive integers $d_i$, meaning that node $i$ in the tree corresponds to node $d_i$ in the Trie. It is guaranteed that $2 \le d_i \le m$.

Output Format

Output one integer: the answer modulo $998244353$.

3 17
2 0 2
0 1 2 3 4 5 6 7 8 4 10 11 12 3 14 15 16
0mayqueenkingrket
9 13 17

12

Hint

[Sample $1$ Explanation]

All $S(x)$ are:

$S(1) = \texttt{"mayqueen"}$

$S(2) = \texttt{"mayking"}$

$S(3) = \texttt{"market"}$

All $f(\mathrm{LCP}(S(x), S(y)))$ are:

$f(\mathrm{LCP}(S(1), S(2))) = f(\mathrm{LCP}(\texttt{"mayqueen"}, \texttt{"mayking"})) = f(\texttt{"may"}) = \mathrm{Len}(\texttt{"may"}) = 3$

$f(\mathrm{LCP}(S(1), S(3))) = f(\mathrm{LCP}(\texttt{"mayqueen"}, \texttt{"market"})) = f(\texttt{"ma"}) = \mathrm{Len}(\texttt{"ma"}) = 2$

$f(\mathrm{LCP}(S(2), S(3))) = f(\mathrm{LCP}(\texttt{"mayking"}, \texttt{"market"})) = f(\texttt{"ma"}) = \mathrm{Len}(\texttt{"ma"}) = 2$

All $f([u, v])$ are:

$f([1,2]) = f(\mathrm{LCP}(S(1), S(2))) = 3$

$f([1,3]) = f(\mathrm{LCP}(S(1), S(2))) + f(\mathrm{LCP}(S(1), S(3))) + f(\mathrm{LCP}(S(2), S(3))) = 3 + 2 + 2 = 7$

$f([2,3]) = f(\mathrm{LCP}(S(2), S(3))) = 2$

Therefore:

$f(T) = f([1,2]) + f([2,3]) + f([1,3]) = 3 + 7 + 2 = 12$

[Constraints and Conventions]

This problem uses bundled testdata.

Subtask 1 (3 points): $n, m \le 10$, time limit 1s.
Subtask 2 (5 points): $n, m \le 100$, time limit 1s.
Subtask 3 (9 points): $n, m \le 1000$, time limit 1s.
Subtask 4 (7 points): $n, m \le 5000$, time limit 2s.
Subtask 5 (9 points): $n, m \le 20000$, time limit 3s.
Subtask 6 (11 points): $n, m \le 10^5$, time limit 4s.
Subtask 7 (19 points): $m = 2$, time limit 3s.
Subtask 8 (37 points): no special restrictions, time limit 10s.

For $100\%$ of the testdata, $2 \le n, m \le 3\times 10^5$.

Translated by ChatGPT 5