간단한 트리 문제

$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$ or $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$로 나눈 나머지를 출력한다.