Kanade Loves Maze Designing

Kanade is designing a mini-game. It's a puzzle game that orders players to get out of a maze. Players should also collect as many kinds of elements as they can to gain a better score.

For the easy mode, the maze can be described as a tree. There are $n$ crossings and $n-1$ undirected passages which make the $n$ crossings connected. The $n$ crossings is numbered with integers from $1$ to $n$. Exactly one element is placed on each crossing. The kind of element placed at crossing $i$ is denoted by an integer $c_i$ in the range $[1,n]$.

To evaluate the maze's difficulty, Kanade wants to know how many kinds of elements appear on $p(u,v)$ for every two integers $u,v\in [1,n]$. $p(u,v)$ indicates the simple path from crossing $u$ to crossing $v$ in the maze.

The first line of input contains one integer $T\ (1\le T\le 10)$, indicating the number of test cases.

For each test case, the first line contains one integer $n\ (2\le n\le 2000)$, indicating the number of crossings in the maze.

The second line contains $n-1$ integers $p_2,p_3,\ldots ,p_n\ (p_i<i)$, indicating that the $i$-th crossing is connected with the $p_i$-th crossing by a passage.

The third line contains $n$ integers $c_1,c_2,\ldots, c_n\ (1\le c_i\le n)$, indicating that the kind of element placed at crossing $i$ is $c_i$.

It is promised that for all test cases, $\sum n\le 5000$.

For each test case, output $n$ lines. Each line contains two integers. Let $a_{i,j}$ be the number of kinds of elements appear on $p(i,j)$. Let
$$
f(i,x)=\sum_{j=1}^n a_{i,j}x^{j-1}
$$
Then for the $i$-th line, output $f(i,19560929)\bmod (10^9+7)$ and $f(i,19560929)\bmod (10^9+9)$, space separated.

1
6
1 1 2 2 3
1 1 4 5 1 4

495644981 518101442
495644981 518101442
397599492 896634980
612255048 326063507
495644981 518101442
397599492 896634980

Let A=(aij), then for the example, A equals to
1 1 2 2 1 2
1 1 2 2 1 2
2 2 1 3 2 1
2 2 3 1 2 3
1 1 2 2 1 2
2 2 1 3 2 1

2021“MINIEYE杯”中国大学生算法设计超级联赛（4）