题目内容

在一棵有 $n$ 个节点的树上，每个节点有一个状态，只能为 0 或 1。定义 $v(u,v)$ 为从节点 $u$ 到节点 $v$ 的简单路径上经过的所有节点的状态按次序组成的二进制数（以 $u$ 为最高位，$v$ 为最低位）所对应的十进制值对 $10^9+7$ 取模的结果。

给定初始状态和 $m$ 次操作，操作分为两种：

• 类型 $1$ $u$ $v$：将路径 $u$ 到 $v$ 上每个节点的状态翻转（0 变 1，1 变 0）。
• 类型 $2$ $u$ $v$：查询 $v(u,v)$ 的值。

你需要对于每个类型 $2$ 操作输出答案。

数据范围：节点个数 $n$ 和操作次数 $m$ 均不超过 $2 imes 10^5$。节点编号从 $1$ 到 $n$。初始状态只可能是 0 或 1。所有运算均在模 $10^9+7$ 下进行。

输入描述

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 2 imes 10^5$)，表示树的节点数与操作次数。 第二行包含 $n$ 个整数 $a_1,\dots,a_n$，其中 $a_i$ 为节点 $i$ 的初始状态 ($a_i \in \{0, 1\}$)。 接下来 $n-1$ 行，每行两个整数 $u_i, v_i$ ($1 \le u_i, v_i \le n$)，表示一条边连接节点 $u_i$ 和 $v_i$。 接下来 $m$ 行，每行三个整数 $t, u, v$ ($t \in \{1,2\},\ 1 \le u, v \le n$)，表示一次操作。$t=1$ 为翻转操作，$t=2$ 为查询操作。

输出描述

对于每个类型 $2$ 操作，输出一行一个整数，表示该路径的 $v(u,v)$ 的值。

样例1

输入

3 3
1 0 1
1 2
2 3
2 1 3
1 1 3
2 1 3

输出

5
2

说明

初始状态：节点 1 为 1，节点 2 为 0，节点 3 为 1。

第一条操作查询 $v(1,3)$：路径经过节点 1 $ o$`2`$ o$ 3，状态依次为 1,0,1，构成二进制数 $101_2$，对应十进制 $5$，因此输出 5。

第二条操作翻转路径 1 到 3 上所有节点状态，原状态 1,0,1 变为 0,1,0。

第三条操作再次查询 $v(1,3)$：路径状态变为 0,1,0，二进制 $010_2=2$，输出 2。

样例2

输入

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

输出

6
0
0

说明

初始状态：节点 1=1，2=1，3=0，4=0。

查询 $v(4,3)$：路径为 4 $ o$`2`$ o$`1`$ o$ 3，状态依次为 0,1,1,0，二进制 $0110_2=6$，输出 6。

翻转路径 1 到 2（包含节点 1 和 2），状态变为 0,0,0,0。

查询 $v(3,4)$：路径 3 $ o$`1`$ o$`2`$ o$ 4，状态全 0，结果为 0。

查询 $v(1,4)$：路径 1 $ o$`2`$ o$ 4，全 0，结果为 0。

样例3

输入

1 1
1
2 1 1

输出

1

说明

单节点树，节点 1 状态为 1。查询 $v(1,1)$：路径只包含节点 1，二进制值为 $1_2=1$，模 $10^9+7$ 得 1。这是一个简单的边界情况。