23497번 - Determination 다국어

문제

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.

제한

힌트