Chiaki 有一个 $n \times n$ 的矩阵 $M$，定义如下：

1. 对于每个 $i \in \{1, 2, \dots, n\}$，$M_{i,i} = d_i$。
2. 对于每个 $i \in \{2, 3, \dots, n\}$，$M_{p_i,i} = a_i$，$M_{i,p_i} = b_i$。
3. 其他情况下，$M_{i,j} = x$。

给定 $d_i, p_i, a_i, b_i$ 和 $x$ 的值，求 $\det(M) \pmod{10^9 + 7}$。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10^6$)，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $x$ ($1 \le n \le 10^6, 0 \le x \le 10^9$)。第二行包含 $n$ 个整数 $d_1, d_2, \dots, d_n$ ($0 \le d_i \le 10^9$)。接下来的 $(n - 1)$ 行中，第 $i$ 行包含三个整数 $p_{i+1}, a_{i+1}, b_{i+1}$ ($1 \le p_{i+1} \le i, 0 \le a_{i+1}, b_{i+1} \le 10^9$)。

所有 $n$ 的总和不超过 $10^6$。

输出格式

对于每组测试数据，输出一个整数表示答案。

样例

输入 1

3
1 23333
233
3 1
1 1 1
1 2 3
1 4 5
3 1
2 3 4
1 4 5
2 6 7

输出 1

233
1000000003
999999923