In a town, there are ~N~ people, numbered from ~1~ to ~N~, where each person is a truthteller or a liar. A truthteller always tells the truth, and a liar always lies. Initially, no information is known about the people.

On each of the following ~M~ days, a single statement is made. Each statement is in one of the following forms:

• 1 A B A says that B is a truthteller.
• 2 A B A says that B is a liar.
• 3 A B A says that B is of the same type of A. More specifically, A claims that A and B are either both truthtellers or both liars.
• 4 A B A says that B is of a different type than A. More specifically, A claims that out of A and B, exactly one of them will be a truthteller.

Note that if A is a liar, then the statement made will also be a lie.

After each day, determine the number of possible states of the town that are consistent with all statements (note that this may be zero). Two states of the town differ if there exists a person which is a truthteller in one state, and a liar in the other state. Report this number modulo ~10^9+7~.

Constraints

~1 \le N \le 10^9~

~1 \le M \le 2 \times 10^5~

~1 \le A, B \le N~, ~A \ne B~

Subtask 1 [40%]

Only statements of type 2 are made.

Subtask 2 [20%]

Only statements of types 1 and 2 are made.

Subtask 3 [40%]

No additional constraints.

Input Specification

The first line contains two space separated integers ~N~, ~M~. Each of the following ~M~ lines contains three space-separated integers, representing a statement made. They will be in the format described above.

Output Specification

Print ~M~ integers, one on each line. The ~i~-th integer should be the number of possible states of the town after the first ~i~ statements are made, modulo ~10^9+7~.

Sample Input

2 2
1 1 2
4 1 2

Sample Output

2
1

Explanation

After the second statement is made, the only possible state of the town is that everyone is a liar. Then, both statements made are false, which is consistent with person 1 being a liar.