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 … 𝑠𝑛 (𝑠𝑖 = 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.

Sample Input

3 0

Sample Output

8

Sample Input

6 1
1 4 3

Sample Output

8

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.