410474: GYM104024 F Subsequence
Description
Aqua and Hiyori love subsequences.
Today, Aqua finds a cute tree. A tree is an undirected acyclic graph and this cute tree's root is vertex $$$1$$$. Now, Aqua colors the vertices in the tree and the color of vectex $$$i$$$ is $$$a_i$$$. In order to examine Aqua, Hiyori sets a problem.
A subsequence $$$A$$$ is defined as some sequences like $$$\lbrace u_1,u_2,\cdots,u_k\rbrace(k\geq 1)$$$, and it satisfies that $$$u_i$$$ is $$$u_{i+1}$$$'s ancestor for every $$$i=1,2,\cdots,k-1$$$. Meanwhile, the color of the subsequence $$$A$$$ is $$$\lbrace a_{u_1},a_{u_2},\cdots,a_{u_k}\rbrace$$$.
Define $$$T$$$ as the multiset of all subsequences' color in the tree, and $$$P(T)$$$ as the set of all subsequences' color in the tree. Let $$$v_x$$$ be the number of the subsequence $$$x$$$'s color appearing in $$$T$$$.
Now, Aqua should get $$$\sum_{x\in P(T)} v_x^2$$$. But she is stupid, could you help her?
InputThere are three lines in the input.
The first line contains a integer $$$n\ (1\leq n\leq 5\cdot 10^3)$$$, represents the size of tree.
The second line contains $$$n$$$ integers $$$a_1,a_2,\cdots,a_n\ (0\leq a_i\leq 10^9)$$$, represents the color of vertex $$$i$$$.
The third line contains $$$n-1$$$ integer $$$p_2,p_3,\cdots,p_n\ (1\leq p_i\leq i-1)$$$, represents the father of vertex $$$i$$$.
OutputPrint one line. The only line should contain the answer modulo $$$998244353$$$.
ExamplesInput3 1 2 3 1 1Output
5Input
3 1 1 1 1 1Output
13Note
In the second sample, $$$T=\lbrace \lbrace 1\rbrace,\lbrace 1\rbrace,\lbrace 1\rbrace,\lbrace 1,1\rbrace,\lbrace 1,1\rbrace\rbrace, P(T)=\lbrace\lbrace 1\rbrace,\lbrace 1,1\rbrace\rbrace$$$, so the answer is $$$3^2+2^2=13$$$.