Sau khi cùng đồng đội giải mã các mệnh lệnh, Phong dần chìm vào giấc ngủ. Trong mơ, anh thấy cảnh nhân dân đang hân hoan trong niềm vui giành được chính quyền. Cờ sao phấp phới tung bay, những cánh chim bay lượn tự do trên bầu trời như muốn hòa nhịp cùng hàng vạn người dân ở dưới.

Bỗng một ánh sáng chói lóa từ bầu trời rọi xuống, bao quanh người Phong, khiến anh bừng tỉnh. Anh đã được đưa trở lại thực tại, trong gian phòng đầy những trang sách lịch sử. Kế bên anh là một bức thư không biết xuất hiện từ bao giờ. Đó là thư mời những người thanh niên ưu tú như Phong đến tham dự một trong những buổi huấn luyện đầu tiên cho nhiệm vụ A80 – nhiệm vụ luyện tập và tham gia diễu binh, diễu hành trong Lễ kỷ niệm 80 năm Cách mạng tháng Tám thành công (19/8/1945 – 19/8/2025) và Quốc khánh nước Cộng hòa Xã hội Chủ nghĩa Việt Nam (2/9/1945 – 2/9/2025).

Sáng hôm sau, Phong đến điểm hẹn trong thư. Ánh nắng đầu ngày trải dài trên quảng trường rộng lớn. Những hàng cây ven đường đổ bóng xuống nền gạch đỏ, nơi hàng ngàn bước chân đang dập đều theo nhịp trống. Trên khán đài nhỏ đặt ở góc sân, Phong đứng lặng, đôi mắt dõi theo từng hàng quân diễu bước.

Tiếng hô "Một! Hai!" vang vọng khắp không gian. Dưới nắng sớm, những bộ quân phục xanh, trắng, những lá cờ đỏ sao vàng rực rỡ cùng tung bay. Nhịp bước chắc nịch, ánh mắt kiên định, tất cả tạo thành bức tranh sống động của sức trẻ. Phong cảm nhận rất rõ, trong từng cử động ấy, có cả âm hưởng của những năm tháng lịch sử mà anh vừa được sống lại.

Người chỉ huy tiến tới, mời Phong cùng tham gia quan sát từ vị trí gần hơn. "Chúng tôi muốn thế hệ trẻ tận mắt chứng kiến và tự hào về sự trang nghiêm của đội hình," ông nói. Phong gật đầu, bước xuống sân. Khi khoảng cách gần hơn, anh càng cảm nhận rõ hơn hơi thở của tuổi trẻ: mồ hôi ướt đẫm áo, nhưng gương mặt ai cũng sáng ngời quyết tâm.

Một khoảnh khắc, mắt Phong dừng lại trên lá cờ lớn đang tung bay ở đầu đội hình. Ánh sao vàng chói lòa trong nắng sớm, rực rỡ chẳng khác nào lá cờ năm xưa anh đã từng nhìn thấy bay trong sương trắng của thung lũng. Hình ảnh ấy khiến trái tim anh bồi hồi. Quá khứ và hiện tại, như hai nhịp đập nối liền, cùng hòa chung trong bước đi của dân tộc.

Trong buổi huấn luyện, những thanh niên trẻ tập hô khẩu hiệu. Tiếng hô dội lên, đồng thanh, dõng dạc, như khẳng định tinh thần sắt son với Tổ quốc. Phong chợt nhớ đến những ngày người dân kéo về quảng trường cách đây tám mươi năm, cũng hô vang những khẩu hiệu tương tự, cũng xếp thành đội ngũ gọn gàng, nhưng trong tay không phải vũ khí, mà là niềm tin và khát vọng tự do.

Bầu trời trên quảng trường trong xanh lạ thường. Tiếng chim buổi sớm bay lượn phía xa. Trong nhịp bước của những người trẻ, Phong nghe thấy không chỉ là tiếng diễu binh, mà còn là tiếng vọng từ quá khứ, tiếng gọi của tương lai. Anh hiểu rằng, mình may mắn được chứng kiến hai thời khắc lịch sử: những buổi chuẩn bị cho chiến dịch năm 1945, và một buổi sáng hôm nay – khi cả dân tộc đang chuẩn bị cho ngày hội lớn kỷ niệm 80 năm Cách mạng tháng Tám và Quốc khánh.

Đến lúc nghỉ ngơi, qua lời một chỉ huy đội hình cho biết, việc sắp xếp những người lính sao cho đội hình đồng đều, ngay ngắn là một việc vô cùng quan trọng. Đầu tiên, những người lính sẽ được cho chiều cao. Dựa vào đó, họ sẽ được gán mã số ~1, 2, 3, \dots, N~ theo thứ tự chiều cao tăng dần. Biết rằng, để đội hình đều và đẹp nhất khi nó thỏa đồng thời ~M~ điều kiện có dạng:

• Điều kiện được mô tả bởi ba số nguyên ~L, R, x~, trong đó ~L \leq x \leq R~, cho biết rằng chỉ huy đội hình yêu cầu người lính thấp nhất trong số các người lính ở vị trí ~L, L + 1, L + 2, \dots, R - 1, R~ phải không được đứng ở vị trí ~x~. Nói cách khác, cần sếp đội hình sao cho ~P_x \neq \min_{L \le i \le R} P_i~, với ~P_j~ là mã số của người lính ở vị trí ~j~.

Chỉ huy đã tìm ra được một đội hình ưng ý rồi, nhưng Phong vẫn thắc mắc, với ~M~ điều kiện như vậy thì có bao nhiêu cách sắp xếp đội hình~^\dagger~ thỏa mãn tất cả. Do đội hình khá đông và một mình Phong không tính được, nên Phong nhờ bạn tính giúp và cho Phong kết quả. Kết quả có thể rất lớn nên bạn chỉ cần in ra phần dư của đáp án khi chia cho ~19450819~.

~\dagger~ Hai cách xếp đội hình ~A, B~ được xem là khác nhau nếu tồn tại một vị trí có hai người lính khác nhau ở hai cách xếp, tức tồn tại ~j~ sao cho ~A_j \neq B_j~.

Input

• Dòng đầu tiên chứa hai số nguyên ~N, M~ là số người lính và những điều kiện cần thoả mãn.

• Trong ~M~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~L, R, x~ mô tả một điều kiện (~1 \leq L \leq x \leq R \leq n~).

Output

• Gồm một dòng là số đội hình thoả cả ~m~ yêu cầu, chia lấy dư cho ~19450819~.

Scoring

Sample Input 1

3 3
1 3 2
2 3 2
1 2 2

Sample Output 1

2

Sample Input 2

7 7
6 7 7
2 7 2
5 6 6
5 7 7
2 5 5
5 7 6
2 6 3

Sample Output 2

140

Sample Input 3

5 2
2 5 4
4 5 4

Sample Output 3

60

Notes

Ở test ví dụ đầu tiên, hai cách xếp đội hình thỏa mãn yêu cầu đề bài là ~[1, 3, 2]~ và ~[2, 3, 1]~.