Zhang 教授有一棵有根树，顶点编号为 $1, 2, \dots, n$。第 $i$ 个顶点有一个整数权值 $w_i$。

对于每个 $s \in \{1, 2, \dots, n\}$，Zhang 教授想要找到一个顶点序列 $v_1, v_2, \dots, v_m$，使得：

• $v_1 = s$，且对于每个 $1 < i \le m$，$v_i$ 是 $v_{i-1}$ 的祖先。
• 值 $f(s) = w_{v_1} + \sum_{i=2}^{m} (w_{v_i} \text{ op } w_{v_{i-1}})$ 最大。这里，运算 $x \text{ op } y$ 是两个整数的按位与（AND）、或（OR）或异或（XOR）运算。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ 和一个字符串 $\text{op}$ ($2 \le n \le 2^{16}, \text{op} \in \{\text{AND, OR, XOR}\}$ )，分别表示顶点数和运算类型。 第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$ ($0 \le w_i < 2^{16}$)。 第三行包含 $n-1$ 个整数 $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$)，其中 $p_i$ 是顶点 $i$ 的父节点。

测试数据约有 300 组，且所有测试数据中 $n$ 的总和不超过 $10^6$。

输出格式

对于每组测试数据，输出整数 $S = \left( \sum_{i=1}^{n} i \cdot f(i) \right) \pmod{10^9 + 7}$。

样例

输入 1

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

输出 1

91
139
195