You are given two integers n(1≤n≤105) and m (1≤m≤105). 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 ai = ai 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 (109+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≤n≤105
- 0≤m≤105
- 1≤l≤r≤n
- 0≤x≤230−1
if we apply query on position i, ai is 1 else 0. so there 8 different arrays
