Fibonacci em Árvore

#187
Made by: Crazynds
1000MB
1s

Dada uma árvore com $N$ nós enumerados de $1$ a $N$. Cada nó $i$ possui um valor inteiro $w_i$. Processe $Q$ operações:

  • 1 u v x: Adicione $x$ ao valor de todos os nós no caminho simples de $u$ até $v$ (inclusive).
  • 2 u v: Calcule $\displaystyle\sum_{i \in \text{path}(u,v)} F(w_i) \pmod{10^9+7}$, onde $F(k)$ é o $k$-ésimo número de Fibonacci com $F(0)=0,\ F(1)=1,\ F(2)=1,\ F(3)=2,\ \ldots$

Input

A primeira linha contém dois inteiros $N$ e $Q$.

A segunda linha contém $N$ inteiros $w_i$.

As próximas $N-1$ linhas contêm dois inteiros $u$ e $v$, representando uma aresta da árvore.

As próximas $Q$ linhas contêm cada uma uma operação no formato descrito.

$$1 \le N,, Q \le 5 \times 10^4, \quad 0 \le w_i \le 10^9, \quad 1 \le x \le 10^9$$

Output

Para cada operação do tipo 2, imprima a resposta em uma linha separada.

Input Example
Output Example 
5 3
1 2 3 4 5
1 2
2 3
3 4
4 5
2 1 3
1 1 3 2
2 2 4

4
11

1 5
1
2 1 1
1 1 1 5
2 1 1
1 1 1 1000000000
2 1 1

1
8
1

2 5
1 1
1 2
2 1 2
1 1 2 1
2 1 2
2 1 1
2 2 2

2
2
1
1

3 6
1 2 3
1 2
2 3
2 1 1
2 2 2
2 3 3
2 1 2
2 2 3
2 1 3

1
1
2
2
3
4

5 10
1 0 1 0 1
1 2
2 3
3 4
4 5
1 1 5 1000000000
1 1 5 1000000000
1 1 5 1000000000
1 1 5 1000000000
1 1 5 1000000000
1 1 5 1000000000
1 1 5 1000000000
1 1 5 1000000000
1 1 5 1000000000
2 1 5

459739080

7 10
12 20 9 2 15 18 4
1 2
1 3
2 4
2 5
3 6
3 7
1 4 1 592749117
2 3 7
1 6 5 950746572
2 7 3
1 5 2 756528253
2 1 1
1 6 2 830075811
2 3 1
1 7 2 930379757
2 1 4

37
392498699
461828057
562441017
296320956