Problem Description
Professor Zhang has a rooted tree, whose vertices are conveniently labeled by 1,2,...,n. And the i-th vertex is assigned with weight wi.
For each s∈{1,2,...,n}, Professor Zhang wants find a sequence of vertices v1,v2,...,vm such that:
Input
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains an integer n and a string opt (2≤n≤216,opt∈{AND,OR,XOR}) -- the number of vertices and the operation. The second line contains n integers w1,w2,...,wn (0≤wi<216). The thrid line contain n−1 integers f2,f3,...,fn (1≤fi<i), where fi is the father of vertex i.
There are about 300 test cases and the sum of n in all the test cases is no more than 106.
Output
For each test case, output an integer S=(∑i=1ni⋅f(i)) mod (109+7).
Sample Input
3
5 AND
5 4 3 2 1
1 2 2 4
5 XOR
5 4 3 2 1
1 2 2 4
5 OR
5 4 3 2 1
1 2 2 4
Sample Output
91
139
195