Bạn được biết \(m\) mô tả về dãy bit. Mỗi mô tả có thể thuộc một trong hai loại sau:

• \(1\) \(l\) \(r\): Dãy bit con \([l, r]\) chứa ít nhất một bit \(0\).
• \(2\) \(l\) \(r\): Dãy bit con \([l, r]\) chứa ít nhất một bit \(1\).

Nhiệm vụ của bạn là đếm số lượng dãy bit có độ dài \(n\) sao cho nó khớp với mô tả trên.

Input

• Dòng đầu tiên chứa hai số \(n\) và \(m\) \((1\le n\le 10^{18}, 0\le m\le \min(10^5, n \times (n - 1)))\).
• Tiếp đó là \(m\) dòng, mỗi dòng là một mô tả thuộc một trong hai loại trên \((1 \le l \le r \le n)\).

Output

• In ra kết quả sau khi chia lấy dư cho \(1234567891\).

Scoring

• Subtask \(1\) \((10\%)\): \(m = 0\).
• Subtask \(2\) \((20\%)\): \(n \le 18, m \le \min(36, n \times (n - 1))\).
• Subtask \(3\) \((30\%)\): \(n \le 10^4\).
• Subtask \(5\) \((40\%)\): Không giới hạn gì thêm.

Example

3 2
1 1 2
2 2 3

4