解题思路

这道题需要维护一棵树上的两种操作：

1. 将简单路径 $u \to v$ 上所有点的值反转；
2. 查询简单路径 $u \to v$ 上所有点按路径顺序组成的 01 串对应的二进制值，结果对 $10^9+7$ 取模。

其中 $n,m \le 2 \times 10^5$，显然不能每次操作都直接把整条路径上的点取出来处理，否则最坏会退化到 $O(nm)$，无法通过。

题目内容

小美有一颗节点编号为 $1$ ~ $n$ 的树，每个节点只有 {$0,1$} 这两种值之一。

我们设 $u->v$ 为节点 $u$ 到节点 $v$ 的简单路径。$g(u->v)$ 为从 $u$ 开始到 $v$ 结束的简单路径上经过的所有点(包括 $u,v$)按照先后顺序组成的 $01$ 字符串对应的十进制对 $10^9+7$ 取模的结果。

例如，简单路径 $u->v$ 经过所有节点组成的字符串为 $01101$，其对应十进制就是 $13$，因此 $g(u->v)=13$ $mod (10^9+7)=13$。

小美会进行 $m$ 次以下操作：

• 操作 $1$ ：将简单路径 $u->v$ 上所有节点的值反置。

• 操作 $2$：询问 $g(u->v)$ 的值。

你需要对小美的每一个操作二进行回答。

【反置】若当前字符为 $0$ ，反置后为 $1$ ；若当前字符为 $1$ ，反置后为 $0$ 。

输入描述

第一行输入两个整数 $n,m(1≤n,m≤2×10^5)$ 表示树的大小以及 小美询问的次数。

第二行输入 $n$ 个整数 $a_i(a_i∈${$0,1$}$)$ 表示第 $i$ 个节点初始的值。

接下来 $n-1$ 行，每一行输入两个整数 $u_i,v_i(1≤u_i,v_i≤n)$ 表示节点 $u_i$ 与 $v_i$ 之间有一条边。

接下来 $m$ 行，每一行输入三个整数 $x,u,v(x∈${$1,2$},$1≤u,v≤n)$，具体的：

• $x=1$：将简单路径 $u->v$ 上所有节点的值反置。

• $x=2$：询问 $g(u->v)$ 的值。

输出描述

对于每个操作二，在一行上输出一个整数，表示 $g(u->v)$ 的值。

样例1

输入

5 5
0 0 0 0 0
1 2
1 3
2 4
2 5
2 1 4
1 1 3
2 4 1
1 2 5
2 5 1

输出

0
1
7

说明

第一次询问时得到的字符串为 $000$，第二次询问得到的字符串为 $001$，第三次询问得到的字符串为 $111$。