题目描述
你有一个 $n \times n$ 的矩阵 $M$,下标从 $1$ 开始。
对于 $i \in [1, n], M_{i,i} = c_i$
对于 $i \in [2, n], M_{p_i,i} = a_i, M_{i,p_i} = b_i$
否则 $M_{i,j} = x$ 给定 $a_i, bi, ci, pi, x$,求 $\det(M)$ mod $998244353$。
输入格式
第一行一个数 $T$,表示数据组数。
对于每组数组,第一行两个整数 $n, x$。
然后一行 $n$ 个整数,$c_i$。
然后 $n − 1$ 行,每行三个整数,$p_{i+1}, a_{i+1}, b_{i+1}$。
输出格式
$T$ 行每行一个非负整数,表示答案。
样例1输入
1
3 1
2 3 4
1 4 5
2 6 7
样例1输出
998244269
样例2
见选手目录下 gauss2.in 与 gauss2.ans
数据规模与约定
subtask1($20$ pts): $n \le 300$
subtask2($20$ pts): $p_i = 1$
subtask3($20$ pts): $x = 0$
subtask4($40$ pts): 无特殊限制。
对于 $100\%$ 的数据,保证 $1 \le T \le 5, 1 \le n \le 10^6, 1 \le p_i < i, 0 \le x, a_i, b_i, c_i < 998244353$