Tiến sĩ Astro Insky làm việc tại trung tâm vô tuyến thiên văn. Gần đây, cô nhận thấy có một làn vi sóng lạ phản xạ từ trung tâm thiên hà. Đây có lẽ là thông điệp đến từ một dạng sống thông minh ngoài trái đất. Sau khi phân tích dãy bit \(𝑆\) là dữ liệu một trong các ngày thu nhận được, cô nhận thấy dãy \(𝑆\) có đặc tính sau:

• Độ dài dãy bit \(𝑆\) bằng \(𝑛\), kí hiệu \(𝑆 = 𝑠_1𝑠_2 … 𝑠_𝑛 (𝑠_i = 0\) hoặc \(1\));

• Có \(𝑚\) cặp vị trí \(𝑝_𝑖, 𝑞_𝑖\) mà hai dãy bit liên tiếp độ dài \(𝑙_𝑖 (𝑖 = 1,2, … , 𝑚)\) của \(𝑆\) bắt đầu từ vị trí \(𝑝_𝑖\) và \(𝑞_𝑖\) giống nhau, cụ thể \(𝑠[𝑝_𝑖] = 𝑠[𝑞_𝑖] ; 𝑠[𝑝_{𝑖+1}] = 𝑠[𝑞_{𝑖+1}]; … ; \) \(𝑠[𝑝_{𝑖+𝑙_𝑖−1}] = 𝑠[𝑞_{𝑖+𝑙_𝑖−1}] (1 ≤ 𝑝_𝑖 ≠ 𝑞_𝑖 ≤ 𝑛 − 𝑙_𝑖 + 1). \)

Thật ngạc nhiên, tất cả các dãy bit trong các ngày cô thu nhận được đều có đặc tính như vậy. Để có thể hiểu được thông điệp, cô muốn tính xem có bao nhau dãy bit khác nhau đều có đặc tính đó.

Yêu cầu: Cho \(𝑛\) và \(𝑚\) bộ \(𝑝_𝑖, 𝑞_𝑖, 𝑙_𝑖 (1 ≤ 𝑝_𝑖 ≠ 𝑞_𝑖 ≤ 𝑛 − 𝑙_𝑖 + 1)\), hãy đếm số dãy bit độ dài \(𝑛\) mà với mỗi bộ \(𝑝_𝑖, 𝑞_𝑖, 𝑙_𝑖\) thì hai dãy bit liên tiếp độ dài \(𝑙_𝑖 (𝑖 = 1,2, … , 𝑚) \) bắt đầu từ vị trí \(𝑝_𝑖\) và \(𝑞_𝑖\) giống nhau.

Dữ liệu:

• Dòng đầu ghi hai số nguyên \(𝑛, 𝑚; \)

• Tiếp theo là \(𝑚\) dòng, dòng thứ 𝑖\( (𝑖 = 1,2, … , 𝑚)\) chứa ba số nguyên \(𝑝_𝑖, 𝑞_𝑖, 𝑙_𝑖.\)

Kết quả:

• một dòng chứa một số nguyên là phần dư của phép giữa số lượng cách tính được và \(10^9+7. \)

Ràng buộc:

Có 25% số lượng test thỏa mãn điều kiện: \(𝑛 ≤ 200; 𝑚 = 0; \)

Có 25% số lượng test khác thỏa mãn điều kiện: \(𝑛 ≤ 200; 𝑚 ≤ 200; \)

Có 25% số lượng test khác thỏa mãn điều kiện: \(𝑛 ≤ 2000; 𝑚 ≤ 2000; \)

Có 25% số lượng test còn lại thỏa mãn điều kiện: \(𝑛 ≤ 10^5; 𝑚 ≤ 10^5. \)

Sample Input

3 0

Sample Output

8

Sample Input

6 1
1 4 3

Sample Output

8