This is the hard version of the problem. The difference between the versions is that in this version, $$$n \le 5 \cdot 10^5$$$. You can hack only if you solved all versions of this problem.

Given a tree $$$T$$$ with $$$n$$$ vertices rooted at $$$1$$$ and a sequence $$$a$$$ of length $$$n$$$, count the number of permutations$$$^{\text{∗}}$$$ $$$p$$$ of length $$$n$$$ that satisfy the following condition:

For all $$$1 \le u \le n$$$, there are exactly $$$a_u$$$ vertices $$$v$$$ such that $$$v$$$ is an ancestor of $$$u$$$ in $$$T$$$ and $$$p_v \lt p_u$$$.

Output the answer modulo $$$998\,244\,353$$$. Input data is selected in such way, such that it's guaranteed that at least one valid permutation exists.

$$$^{\text{∗}}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 5000$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 5 \cdot 10^5$$$) — the number of vertices.

The second line of each test case contains $$$n-1$$$ integers $$$fa_2,fa_3,\ldots,fa_n$$$ ($$$1 \le fa_i \lt i$$$)— $$$fa_i$$$ is the parent of $$$i$$$ on $$$T$$$.

The third line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \lt n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$. Input data is selected in such way, such that it's guaranteed that at least one valid permutation exists.

Output

For each test case, output one integer — the number of permutations modulo $$$998\,244\,353$$$.

Note

Visualizer link

In the first test case, the only permutation which satisfies the condition is $$$[1,2,3,4,5]$$$.

In the second test case, permutations which satisfy the condition are $$$[4,5,1,2,3],[4,5,1,3,2],[4,5,2,1,3],[4,5,2,3,1],[4,5,3,1,2],[4,5,3,2,1]$$$.

In the third test case, permutations which satisfy the condition are $$$[3,1,6,2,5,7,8,4],[3,1,6,2,5,8,7,4],[3,2,6,1,5,7,8,4],[3,2,6,1,5,8,7,4]$$$.

Chain Prefix Rank (Hard Version)

Examples