行列式
题目描述
给定 n×n 矩阵 A=(ai,j),求 det(A) 模 109+7。矩阵由下列参数定义:
$$a_{i,j}=\begin{cases}
b_j,&i=p_j,\\
c_i,&j=p_i,\\
d_i,&i=j,\\
x,&\text{其他情况}。
\end{cases}$$
其中 d1,…,dn 为对角线元素,pi,bi,ci (2≤i≤n) 和常数 x 给定,且 pi<i。
输入格式
第一行一个正整数 n 和非负整数 x。
第二行 n 个非负整数 d1,…,dn。
接下来 n−1 行,第 i−1 行给出 pi,bi,ci (2≤i≤n)。
输出格式
输出行列式模 109+7。
补充样例输入
2 1
2 3
1 4 5
补充样例输出
999999993
矩阵为 (2543),行列式为 −14。
补充样例 2
3 1
1 2 3
1 4 5
2 6 7
999999968
矩阵为 151427163,行列式为 −39。
数据范围
全部数据满足 $1\le n\le10^6,\ 0\le b_i,c_i,d_i,x\le10^9,\ 1\le p_i<i$。
| 子任务 |
分值 |
限制 |
| 1 |
20 |
n≤300 |
| 2 |
15 |
pi=1,n≤105 |
| 3 |
25 |
x=0,n≤105 |
| 4 |
40 |
无 |