Description

有n对夫妇,一开始夫妇之间互不认识,若两男或两女成为朋友,称他们为"熟人","熟人"关系具有传递性,即若a熟b且b熟c则a熟c.若两组夫妇的丈夫互相为熟人且妻子也相互为熟人则称他们为"熟悉的一对",现在给出q个事件,每个事件会使得两男或两女成为朋友,并在每次事件之后计算"熟悉的一对"的个数.

Format

Input

第一行一个数T表示数据组数

接下来n,q表示对数和事件数

接下来q行,每行t,a,b,若t=1,表示男a和男b成为朋友,t=2,表示女a和女b成为朋友

Output

设当前是第i个操作,y_i为本次事件之后的答案,令z_i=i*y_i,请输出z_1+z_2+...+z_q模10^9+7

Samples

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

22

Limitation

样例解释 10+20+31+41+5*3=22

T<=8

n,q<=10^6