MofK có 1 xâu nhị phân ~s~ (xâu chỉ gồm các kí tự ~0~ hoặc ~1~) độ dài ~n~, các kí tự được đánh số từ ~0~ đến ~n-1~. ngk muốn biết xâu ~s~, nhưng thay vì nói thẳng, MofK chỉ đưa cho ngk ~m~ gợi ý có dạng ~c\ l\ r\ k~, trong đó nếu ~c = 0~ thì xâu con ~[l..l+k]~ (gồm các kí tự có chỉ số từ ~l~ đến ~l+k~) bằng xâu con ~[r..r+k]~, còn nếu ~c = 1~ thì xâu con ~[l..l+k]~ ngược hoàn toàn xâu con ~[r..r+k]~, có nghĩa là mọi vị trí tương ứng của 2 xâu đó đều khác nhau.

ngk cho rằng MofK đưa chưa đủ gợi ý để đoán chính xác xâu ~s~, hay có thể đưa ra gợi ý sai, nên ngk muốn tính xem có bao nhiêu xâu nhị phân độ dài ~n~ thỏa mãn cả ~m~ điều kiện đã cho.

Input

Dòng đầu tiên gồm hai số nguyên ~n~ và ~m~ (~n,m\le 200000~).

~m~ dòng tiếp theo, mỗi dòng gồm bốn số nguyên ~c, l, r, k~ (~0\le c\le 1, 0\le l\le r\lt n,k\le n -1 - r~) mô tả một gợi ý.

Output

In ra số xâu nhị phân độ dài ~n~ thỏa mãn cả ~m~ gợi ý modulo ~10^9+7~ trên một dòng.

Scoring

Subtask ~1~ (~10\%~): ~n,m\le 15~

Subtask ~2~ (~30\%~): ~n,m\le 5000~

Subtask ~3~ (~60\%~): Không có ràng buộc gì thêm.

Sample Input 1

4 2
0 0 2 1
1 0 1 0

Sample Output 1

2