간단한 트리 문제

$N$개의 정점과 $N-1$개의 간선으로 이루어진 트리가 있다. 각 정점에는 $1$번부터 $N$번까지, 각 간선에는 $1$번부터 $N-1$번까지 번호가 붙어 있으며 모든 정점과 간선에는 가중치가 부여되어 있다. 다음 쿼리를 처리하는 프로그램을 작성하시오.

• $1$ $i$ $x$ : $i$번 정점의 가중치를 $x$로 변경한다.
• $2$ $i$ $x$ : $i$번 간선의 가중치를 $x$로 변경한다.

최초 트리 상태와 각 변경 쿼리마다 모든 $N(N-1)/2$개의 서로 다른 경로에 대하여 (경로 위 정점 가중치의 합)$\times$(경로 위 간선 가중치의 합)의 합을 $10^9+7$로 나눈 나머지를 출력하시오.

첫째 줄에 정점의 수 $N$과 쿼리의 수 $Q$가 공백을 사이에 두고 주어진다. ($2 \leq N \leq 2 \times 10^5, 1 \leq Q \leq 2 \times 10^5$)

둘째 줄에 $i$번째 정점의 가중치 $A_i$가 공백을 사이에 두고 주어진다. ($1 \leq A_i \leq 10^9$)

셋째 줄부터 $N+1$번째 줄까지 $i$번째 간선의 정보를 나타내는 세 정수 $u_i$ $v_i$ $w_i$가 공백을 사이에 두고 주어진다. 정점 $u_i$와 정점 $v_i$ 사이에 가중치가 $w_i$인 간선이 있다는 뜻이다.

$N+2$번째 줄부터 $N+Q+1$번째 줄까지 각 쿼리의 정보 $t$ $i$ $x$가 공백을 사이에 두고 주어진다.

$t=1$ 또는 $2$이다. $t=1$이면 $1 \leq i \leq N$이고, $t=2$이면 $1 \leq i \leq N-1$이며, $1 \leq x \leq 10^9$이다.

$Q+1$개의 줄에 걸쳐 정답을 $10^9+7$로 나눈 나머지를 출력한다.