Determination

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$가 주어질 때, $\mathrm{det}(M)$을 $(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$). 각 $i=1,2,\dots,n-1$에 대해 이어지는 $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$을 넘지 않는다.

각 테스트 케이스마다 정답을 나타내는 정수를 한 줄에 출력한다.