{"code":"bitseq","name":"Dãy bit","description":"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:\r\n - $1$ $l$ $r$: Dãy bit con $[l, r]$ chứa ít nhất một bit $0$.\r\n - $2$ $l$ $r$: Dãy bit con $[l, r]$ chứa ít nhất một bit $1$.\r\n\r\nNhiệ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.\r\n\r\n#### Input\r\n - 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)))$.\r\n - 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)$.\r\n\r\n#### Output\r\n - In ra kết quả sau khi chia lấy dư cho $1234567891$.\r\n\r\n#### Scoring\r\n - Subtask $1$ $(10\\%)$: $m = 0$.\r\n - Subtask $2$ $(20\\%)$: $n \\le 18, m \\le \\min(36, n \\times (n - 1))$.\r\n - Subtask $3$ $(30\\%)$: $n \\le 10^4$.\r\n - Subtask $5$ $(40\\%)$: Không giới hạn gì thêm. \r\n    \r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        3 2\r\n        1 1 2\r\n        2 2 3\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        4\r\n        ```\r\n    ??? warning \"Note\"\r\n        - Có $4$ dãy bit thỏa mãn là `001`, `010`, `011`, `101`.","points":2500.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}