시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 256 MB111100.000%

문제

Chiaki has an $n \times n$ matrix $M$ defined as follows.

  1. $M_{i, i} = d_i$ for each $i \in \{1, 2, \dots, n\}$,
  2. $M_{p_i, i} = a_i$, $M_{i, p_i} = b_i$ for each $i \in \{2, 3, \dots, n\}$,
  3. $M_{i, j} = x$, otherwise.

Given the value of $d_i$, $p_i$, $a_i$, $b_i$ and $x$, find $\mathrm{det}(M)$ modulo $(10^9+7)$.

입력

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 10^6$), indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $x$ ($1 \leq n \leq 10^6$, $0 \leq x \leq 10^9$). The second line contains $n$ integers $d_1, d_2, \dots, d_n$ ($0 \leq d_i \leq 10^9$). The $i$-th of the following $(n - 1)$ lines contains three integers $p_{i + 1}, a_{i + 1}, b_{i + 1}$ ($1 \leq p_{i + 1} \leq i$, $0 \leq a_{i + 1}, b_{i + 1} \leq 10^9$). 

The sum of all $n$ does not exceed $10^6$.

출력

For each test case, output an integer denoting the answer.

예제 입력 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