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$