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:
- v1=s and vi is the ancestor of vi−1 (1<i≤m).
- the value f(s)=wv1+∑i=2mwvi opt wvi−1 is maximum. Operation x opt y denotes bitwise AND, OR or XOR operation of two numbers.
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
