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 như sau:

• Độ dài dãy bit 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+k} = s_{q_i+k}~ với mọi ~0 \le k < l_i~ (~1 \le p_i \ne q_i \le n-l_i+1~; ~i=1, 2, \dots, m~).

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 (~i = 1, 2, \dots, m~).

Input

• 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~.

Output

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

Sample Input 1

6 2
1 4 3
3 5 2

Sample Output 1

2