You are given two integers $$n$$($$1 \le n \le 10^5$$) and $$m$$ ($$1 \le m \le 10^5$$). Initially, you have an array $$a$$ of $$n$$ zeros, and $$m$$ applied queries on it. Query is given as $$l$$ $$r$$ $$x$$, where you apply $$a_i$$ = $$a_i$$ xor $$x$$ (xor  denotes the operation bitwise XOR) for every $$i$$ between $$l$$ and $$r$$. But this problem seems boring, so Almas modify some queries interval. By modifying, he applied that operation on a subset of positions on a segment(maybe empty subset). Now he asks you how many different arrays he could have after applying queries. Since the answer can be large, output by modulo 1000000007 ($$10^9 + 7$$).

Input

- In first line, you are given two integers $$n$$ and $$m$$. 

- In next $$m$$ lines, you are given $$l$$ $$r$$ $$x$$. 

Output
-Print in a single line answer by modulo 1000000007.
 

Constraints

- $$1 \leq n \leq 10^5$$

- $$0 \leq m \leq 10^5$$

- $$1 \leq  l \leq  r \leq n$$

- $$0 \leq x \le 2^{30} - 1$$