19433번 - Born Slippy 다국어

문제

Professor Zhang has a rooted tree with vertices conveniently labeled by 1,ドル 2, \ldots, n$. The $i$-th vertex has an integer weight $w_i$.

For each $s \in \{1, 2, \ldots, n\},ドル Professor Zhang wants to find a sequence of vertices $v_1, v_2, \ldots, v_m$ such that:

• $v_1 = s$ and $v_i$ is the ancestor of $v_{i - 1}$ for each 1ドル < i \le m,ドル
• the value $f(s) = w_{v_1} + \sum\limits_{i = 2}^{m} (w_{v_i} \mathrm{op} w_{v_{i - 1}})$ is maximum possible. Here, operation $x \mathrm{op} y$ is the bitwise AND, OR, or XOR operation on two integers.

입력

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 $\mathrm{op}$ (2ドル \le n \le 2^{16},ドル $\mathrm{op} \in \{\mathtt{AND}, \mathtt{OR}, \mathtt{XOR}\}$): the number of vertices and the operation. The second line contains $n$ integers $w_1, w_2, \ldots, w_n$ (0ドル \le w_i < 2^{16}$). The third line contains $n - 1$ integers $p_2, p_3, \ldots, p_n$ (1ドル \le p_i < i$) where $p_i$ is the parent of vertex $i$.

There are about 300ドル$ test cases, and the sum of $n$ in all the test cases is no more than 10ドル^6$.

출력

For each test case, output the integer $S = (\sum\limits_{i = 1}^{n}{i \cdot f(i)})$ modulo 10ドル^9 + 7$.

제한

힌트