问题描述
克拉克是一名人格分裂患者。某一天，克拉克fork出了很多个克拉克，居住在$n$个社区里。
克拉克由于自己的抖M属性，所以克拉克们决定玩饥饿游戏。
由于克拉克们住在天空之城中，所以他们相互联系靠的是社区之间的桥。
克拉克是非常节约的，两个社区能相互可达时只有一条路径，这样就节约了不少金钱。
饥饿游戏的规则是这样的：每一个社区选出两个人，然后作为供品去参加死亡比赛，最终活下一个人，并终身获得自由，获得无限的荣誉和金钱。
克拉克们想知道选出的人中有多少种组合。两个组合相同当且仅当选出的人都相同。
由于克拉克的抖M属性，克拉克还有$q$次操作：
$1 \ u \ v$：在$u, v$两个社区之间建桥。如果$u, v$已经有路径或$u=v$相连则忽略。
$2 \ u \ v$：删除$u, v$两个社区的之间的桥。如果$u, v$之间没有桥或$u=v$则忽略。
$3 \ h$：变回到第$h$次操作后的状态，当$h=0$时表示回到初始状态，即社区之间是没有桥的。
$4 \ u \ v$：询问$u$到$v$路径上的所有社区（包括$u$和$v$）每个社区选出人参加比赛的方案数（如果不存在路径输出$0$），由于方案数太多，所以求出对$10^9+7$取模的答案。
$5 \ u \ s$：社区$u$中的克拉克的数量变为$s$。
一开始克拉克的社区之间是没有桥的。
输入描述
第一行一个整数$T(1 \le T \le 5)$，表示数据的组数。
每组数据第一行有两个整数$n, q(1 \le n, q \le 3*10^5)$。
第二行有$n$个整数，第$i$个数$a_i(0 \le a_i \le 10^4)$表示第$i$个社区的人数。
接下来$q$行，第$i$个询问的第一个数为$opt$。
当$opt=1$时，后面接着两个整数$u_i, v_i$。
当$opt=2$时，后面接着两个整数$u_i, v_i$。
当$opt=3$时，后面接着一个整数$h_i$。
当$opt=4$时，后面接着两个整数$u_i, v_i$。
当$opt=5$时，后面接着两个整数$u_i, s_i$。
$1 \le u_i, v_i \le n, 0 \le h_i < i, 0 \le s_i \le 10^4$
输出描述
对于每组数据的$opt=4$，输出一个整数表示答案。
输入样例
1
3 5
1 2 3
1 1 2
2 1 2
3 1
5 1 3
4 1 2
输出样例
3
Hint
操作1：建了一个连接1、2两个社区的桥。
操作2：删掉1、2两个社区的桥
操作3：回到操作1，即1、2两个社区的桥还存在的时候。
操作4：将1社区的人数改为3
操作5：询问1、2社区每个社区选出两个人的方案数，一共有3种。
