Migrated from Lutece 2724 Namesolo 拜师

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

为了达到 Guapiless 的境界, Namesolo 想要拜伟大的理论计算机科学家 T 姥爷为师。

作为入学测试，T 姥爷给了 Namesolo 一个有 $n$ 个点的无向图， 并要求 Namesolo 在规定时间内反复完成以下两种任务： 1、添加一条连接 $a, b$ 的边； 2、询问 $a, b$ 是否在同一个联通块内，回答 $1$ 表示肯定，$0$ 表示否定。

为了方便 T 姥爷检查答案是否正确，Namesolo 需要将每个询问的答案依次从左到右排列，把得到的串视为一个二进制数，输出这个二进制数 $\bmod 10^9 +7$ 的值。

由于 Namesolo 很 guapi，所以才薄智浅的 ta 无能为力。 由于 Namesolo 很 solo，所以孑然一身的 ta 孤立无援。

路过的你能帮助 Namesolo 完成 T 姥爷的入学测试吗？

Input

第一行给出两个正整数 $n, m$，表示点数和操作次数。 随后 $m$ 行，每行三个正整数 $op, a, b$， 若 $op = 1$ ，表示添加一条连接 $a, b$ 的边， 若 $op = 2$ ，表示查询 $a, b$ 是否在同一个联通块内。

Output

输出一行一个整数，表示答案对应的值对 $10^9 + 7$ 取模的值。

Samples

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

2

Constraints

$1 \le n \le 2^{21}$ ，$1 \le m\le3\times 10^6$ ，$op \in \{1,2\}$ ，$1 \le a,b \le n$ 。 数据不保证无重边和自环。

Note

样例解释：

第一次操作：连接 $3, 4$ ； 第二次操作：连接 $1, 3$ ； 第三次操作：查询 $3, 4$ ，在同一个联通块内，回答 $1$ ； 第四次操作：查询 $4, 2$ ，在不同的联通块内，回答 $0$ ； 此时答案串为 $10$ ，即二进制表示的 $2$ 。

温馨提示：

本题读入量较大，建议使用出题人提供的快速读入模板：

#define getchar() (frS==frT&&(frT=(frS=frBB)+fread(frBB,1,1<<15,stdin),frS==frT)?EOF:*frS++)
char frBB[1<<15],*frS=frBB,*frT=frBB;
template<typename T>
inline void read(T &x){
    x=0;char c=getchar();
    while(!isdigit(c))c=getchar();
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
}
/*
1. 使用 read(x) 读入一个非负整数x
2. 由于 fread 方法特性，本地测试时需要从文件读入，或者注释掉前两行，在提交时取消注释。
*/

Resources

2022 UESTC ICPC Training for Data Structures