Counting Rooted Trees with Preserved LCAs

Let \(T\) be a rooted tree on \(n\) vertices numbered \(1\) through \(n\) with root \(1\) and parent pointers given for nodes \(2,3,\dots,n\). For any two nodes \(u\) and \(v\) in a rooted tree \(G\) we denote by \(\operatorname{lca}_G(u,v)\) their lowest common ancestor in \(G\). You are also given a set \(S\) of \(m\) vertices.

Your task is to count the number of different rooted trees \(T'\) on \(n\) vertices (with vertices labeled \(1\) through \(n\)) such that for every pair \(u, v \in S\) it holds that \[ \operatorname{lca}_T(u,v)=\operatorname{lca}_{T'}(u,v). \] Two rooted trees on \(n\) vertices are considered different if at least one of the following holds:

• Their root nodes are different.
• There is at least one edge that appears in one tree but not in the other.

It can be shown that the answer equals \(n^{n-|X|}\) modulo \(998\,244\,353\), where \(X\) is the set of vertices that lie on the paths from the root to every vertex in \(S\) (including those vertices themselves). In other words, for each \(s \in S\), add \(s\) and all of its ancestors (up to the root) into \(X\). Then the answer is \[ \text{answer} = n^{n-|X|} \pmod{998\,244\,353}. \]

Note: When \(S\) is such that \(X\) is the entire set \(\{1,2,\dots,n\}\) (which happens, for instance, when \(S\) contains at least one leaf from each branch of \(T\)), the only valid tree is \(T\) itself, and the answer is 1.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \le m \le n \le 2\cdot10^5)\), representing the number of vertices and the size of the set \(S\), respectively.

The second line contains \(n-1\) integers \(p_2, p_3, \dots, p_n\) \((1 \le p_i \le n)\) where \(p_i\) is the parent of vertex \(i\) in the tree \(T\). It is guaranteed that \(T\) is a valid rooted tree with root \(1\) (i.e. vertex \(1\) has no parent).

The third line contains \(m\) integers representing the vertices in the set \(S\). The vertices in \(S\) are not necessarily distinct.

outputFormat

Output one integer, the number of different rooted trees \(T'\) that satisfy the given LCA conditions, modulo \(998\,244\,353\).

sample

3 1
1 1
1

9