Clarke and hunger games

Clarke is a patient with multiple personality disorder. One day, Clarke split into a lot of guys, live in $n$ communities.
Clarkes are so boring, so they play a game called hunger games.
They live in a city in the sky, so they connect each other by the bridge between communities.
Clarkes are very economical, so there is only one path between any two communities if they can reach each other.
The rules of the hunger games are like this: each community elects two guys, then send them to participate this death game.
Clarkes want to know how many combinations to elect guys to participate the game, any two combinations are same if and only if the guys selected are same.
Clarkes are so boring, so they have $q$ operations:
1. $u$ $v$: build a bridge between $u$ and $v$. If $u$ and $v$ already have a path connected or $u=v$, ignore.
2. $u$ $v$: remove the bridge between $u$ and $v$. If there is no bridge between $u$ and $v$ or $u=v$, ignore.
3. $h$: back to the state that end of operation $h$. If $h=0$, the state should roll back to the initial state, which has no bridge connecting any two communities.
4. $u$ $v$: ask how many combinations to elect guys from the communities on the path $u$ to $v$(including $u$ and $v$) to participate the game. Since the answer is very large, you only need to output the answer modulo $10^9+7$.
5. $u$ $s$: change the number of the community $u$ to $s$.

At beginning, there is no edge between any two communities.

The first line contains a integer $T(1 \le T \le 5)$, the number of test cases.
For each test case:
The first line contains two integers $u, q(1 \le n, q \le 3*10^5)$.
The second line contains $n$ integers, the $ith$ integer $a_i(0 \le a_i \le 10^4)$denotes the number of the $ith$ communities.
Then $q$ lines follow, the first number is $opt$:
If $opt=1$, then two integers $u_i, v_i$ follow, represent operation $1$
If $opt=2$, then two integers $u_i, v_i$ follow, represent operation $2$
If $opt=3$, then one integer $h_i$ follow, represent operation $3$
If $opt=4$, then two integers $u_i, v_i$ follow, represent operation $4$
If $opt=5$, then two integers $u_i, s_i$ follow, represent operation $5$
$1 \le u_i, v_i \le n, 0 \le h_i < i, 0 \le s_i \le 10^4$

For each testcase, for each $opt=4$, print the answer.

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

3

Hint:
At the beginning, community $1$ has 1 guy, $2$ has 2 guys, $3$ has 3 guys.
Operation 1: build a bridge between $1$ and $2$
Operation 2: remove the bridge between $1$ and $2$.
Operation 3: back to state $1$, which has bridge between $1$ and $2$.
Operation 4: change the number of community $1$ from $1$ to $5$.
Operation 5: enquire the combinations of community $1$ and $2$. Obviously, the answer is 3.

BestCoder Round #56 (div.1) ($)