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.