题目内容

给定一棵包含 $n$ 个节点的树，节点编号 $1$ 到 $n$，每个节点上写有一个数字，且该数字只能是 $0$ 或 $1$。

定义一条简单路径 $u o v$ 按顺序经过节点 $p_1=u, p_2, \dots, p_k=v$，将这些节点的数字依次拼接成一个 01 字符串，将其视为二进制数（$u$ 对应最高位，$v$ 对应最低位），并将该数对 $10^9+7$ 取模的结果记为 $f(u,v)$。

你需要支持 $m$ 次操作，每次操作格式如下：

• 操作 $1$：翻转路径 $u o v$ 上所有节点的数字（$0$ 变为 $1$，$1$ 变为 $0$）；
• 操作 $2$：询问 $f(u,v)$ 的值。

请你对于所有操作 $2$ 给出答案。

数据范围：节点个数 $n$ 与操作次数 $m$ 满足 $1 \le n,m \le 2 imes 10^5$；所有节点上的初始数字均为 $0$ 或 $1$；给出的边构成一棵树。

输入描述

第一行包含两个整数 $n,m$。 第二行包含 $n$ 个整数，依次表示节点 $1$ 到 $n$ 上的初始数字，每个数字为 $0$ 或 $1$。 接下来 $n-1$ 行，每行包含两个整数 $u_i,v_i$，表示树中一条连接节点 $u_i$ 和 $v_i$ 的边。 接下来 $m$ 行，每行包含三个整数 $x,u,v$。其中 $x$ 为 $1$ 或 $2$，表示操作类型；$u,v$ 为路径的端点。

输出描述

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

样例1

输入

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

输出

5
3

说明

初始时，节点数字依次为 1,0,1。 第一个操作 2 1 3 询问路径 $1 o 3$ 上的值。路径经过节点 1 → 2 → 3，对应数字 1,0,1，拼接为二进制 $101_2$，其十进制值为 $5$，对 $10^9+7$ 取模后仍为 5，输出 5。 第二个操作 1 1 2 将路径 $1 o 2$ 上的数字翻转：节点 1 由 1 变为 0，节点 2 由 0 变为 1。此时节点数字变为 0,1,1。 第三个操作 2 3 2 询问路径 $3 o 2$ 上的值。路径经过节点 3 → 2，对应数字 1,1，拼接为二进制 $11_2$，十进制值为 $3$，输出 3。

样例2

输入

1 3
1
2 1 1
1 1 1
2 1 1

输出

1
0

说明

树中只有一个节点 1，初始数字为 1。 第一个操作 2 1 1 询问路径 $1 o 1$ 的值。路径只包含节点 1，二进制为 1，十进制值为 1，输出 1。 第二个操作 1 1 1 翻转节点 1 上的数字，1 变为 0。 第三个操作 2 1 1 再次询问路径 $1 o 1$ 的值。此时节点数字为 0，二进制为 0，十进制值为 0，输出 0。

样例3

输入

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

输出

8
14
9

说明

初始节点数字为 1,0,1,0,0，树形结构：1-2，2-3，2-4，4-5。 第一个操作 2 1 5 询问路径 $1 o 5$。路径为 1 → 2 → 4 → 5，数字依次为 1,0,0,0，拼接为二进制 $1000_2$，十进制值为 $8$，输出 8。 第二个操作 1 2 4 翻转路径 $2 o 4$ 上的数字：节点 2 由 0 变 1，节点 4 由 0 变 1，此时节点数字变为 1,1,1,1,0。 第三个操作 2 3 5 询问路径 $3 o 5$。路径为 3 → 2 → 4 → 5，数字依次为 1,1,1,0，拼接为 $1110_2$，十进制值为 $14$，输出 14。 第四个操作 1 5 1 翻转路径 $5 o 1$，即整条路径 5 → 4 → 2 → 1 上的数字：节点 5 由 0 变 1，节点 4 由 1 变 0，节点 2 由 1 变 0，节点 1 由 1 变 0。节点数字变为 0,0,1,0,1。 第五个操作 2 3 5 再次询问 $3 o 5$。路径 3 → 2 → 4 → 5 的数字依次为 1,0,0,1，拼接为 $1001_2$，十进制值为 $9$，输出 9。