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 ~S~ là dữ liệu một trong các ngày thu nhận được, cô nhận thấy dãy ~S~ có đặc tính như sau:

• Độ dài dãy bit ~S~ bằng ~n~, kí hiệu ~S = s_1s_2s_3 \dots s_n~ (~s_i = 0~ hoặc ~1~);
• Có ~m~ cặp vị trí ~p_i, q_i~ mà hai dãy bit liên tiếp độ dài ~l_i~ của ~S~ bắt đầu từ vị trí ~p_i~ và ~q_i~ giống nhau, cụ thể: ~S[p_i, p_i+l_i-1] = S[q_i, q_i+l_i-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 nhiêu dãy bit khác nhau đều có đặc tính đó.

Yêu cầu: Cho số nguyên ~n~ và ~m~ bộ ~(p_i, q_i, l_i)~, hãy đếm số dãy bit độ dài ~n~ mà với mỗi bộ ~(p_i, q_i, l_i)~ thì hai dãy bit liên tiếp độ dài ~l_i~ bắt đầu từ vị trí ~p_i~ và ~q_i~ giống nhau (với ~i = 1, 2, 3, \dots, m~).

Dữ liệu vào:

Cho trong tệp văn bản MESENGER.INP có cấu trúc như sau:

• Dòng đầu ghi hai số nguyên ~n~, ~m~.
• Tiếp theo là ~m~ dòng, dòng thứ ~i~ chứa ba số nguyên ~p_i~, ~q_i~, ~l_i~. Các số được ghi cách nhau ít nhất một dấu cách.

Dữ liệu ra:

Ghi ra tệp văn bản MESENGER.OUT theo cấu trúc:

• Dòng 1: Ghi một số nguyên là phần dư giữa số lượng đếm được chia cho ~(10^9 + 7)~.

Ví dụ:

Input: MESENGER.INP

6  2
1  4  3
3  5  2

Output: MESENGER.OUT

2

Ràng buộc:

• ~1 \leq n, m \leq 10^5~.