Born Slippy

Zhang 교수는 정점이 $1, 2, \ldots, n$으로 번호가 매겨진 루트 있는 트리를 가지고 있다. $i$번 정점에는 정수 가중치 $w\_i$가 있다.

각 $s \in \{1, 2, \ldots, n\}$에 대해, Zhang 교수는 다음 조건을 만족하는 정점 수열 $v\_1, v\_2, \ldots, v\_m$을 찾으려 한다.

• $v\_1 = s$이고, 각 $1 < i \le m$에 대해 $v\_i$는 $v\_{i - 1}$의 조상이다.
• 값 $f(s) = w\_{v\_1} + \sum\limits\_{i = 2}^{m} (w\_{v\_i} \mathrm{op} w\_{v\_{i - 1}})$가 최대가 된다. 여기서 연산 $x \mathrm{op} y$는 두 정수의 비트 AND, OR, XOR 연산이다.

여러 개의 테스트 케이스가 주어진다. 입력의 첫째 줄에는 테스트 케이스의 수를 나타내는 정수 $T$가 주어진다. 각 테스트 케이스는 다음과 같다.

첫째 줄에는 정수 $n$과 문자열 $\mathrm{op}$가 주어진다 ($2 \le n \le 2^{16}$, $\mathrm{op} \in \{\mathtt{AND}, \mathtt{OR}, \mathtt{XOR}\}$). $n$은 정점의 수이고 $\mathrm{op}$는 연산이다. 둘째 줄에는 $n$개의 정수 $w\_1, w\_2, \ldots, w\_n$이 주어진다 ($0 \le w\_i < 2^{16}$). 셋째 줄에는 $n - 1$개의 정수 $p\_2, p\_3, \ldots, p\_n$이 주어지며, $p\_i$는 정점 $i$의 부모이다 ($1 \le p\_i < i$).

테스트 케이스는 약 $300$개이고, 모든 테스트 케이스에서 $n$의 합은 $10^6$을 넘지 않는다.

각 테스트 케이스에 대해 정수 $S = (\sum\limits\_{i = 1}^{n}{i \cdot f(i)})$를 $10^9 + 7$로 나눈 나머지를 출력한다.