{"code":"pvhoi3debaisieungan","name":"PVHOI3 - Bài 5: Đề bài siêu ngắn","description":"Cho bốn số nguyên dương $n, k, a$ và $b$. Hãy đếm số dãy số nguyên dương $x_{1}, x_{2}, \\ldots, x_{n}$ sao cho:\r\n- Với mọi $1 \\leq i \\leq n, a \\leq x_{i} \\leq b$.\r\n- Bội số chung nhỏ nhất của các số $x_{1}, x_{2}, \\ldots, x_{n}$ chia hết cho $k$.\r\n\r\nDo số lượng dãy có thể rất lớn, bạn chỉ cần in ra kết quả theo modulo $998244353$.\r\n\r\n#### Input\r\n- Gồm một dòng duy nhất chứa bốn số nguyên $n, k, a$ và $b$ $(1 \\leq n \\leq 227,1 \\leq k \\leq 10^{14}, 1 \\leq a \\leq b \\leq 10^{14})$.\r\n\r\n#### Output\r\n- Gồm một số nguyên duy nhất là kết quả của bài toán nêu trên theo modulo $998244353$.\r\n\r\n#### Scoring\r\n- Subtask $1$ ($7$ điểm): $k = 1$\r\n- Subtask $2$ ($8$ điểm): $n \\leq 5, b \\leq 30$ và $k \\leq 30$.\r\n- Subtask $3$ ($9$ điểm): $n \\leq 5$ và $b - a \\leq 30$\r\n- Subtask $4$ ($10$ điểm): $k$ là số nguyên tố\r\n- Subtask $5$ ($16$ điểm): $b \\leq 10^{7}$ và $k \\leq 10^{7}$\r\n- Subtask $6$ ($20$ điểm): Không có ràng buộc gì thêm.\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        2 6 10 14\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        9\r\n        ```\r\n    ??? warning \"Note\"\r\n        Trong ví dụ thứ nhất, các dãy số thoả mãn là $(10, 12)$, $(11, 12)$, $(12, 10)$, $(12, 11)$, $(12, 12)$, $(12, 13)$, $(12, 14)$, $(13, 12)$, $(14, 12)$. \r\n\r\n!!! question \"Test 2\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        3 5 7 9\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        0\r\n        ```\r\n    ??? warning \"Note\"\r\n    \tTrong ví dụ thứ hai, do $7 \\leq x_{i} \\leq 9$ với mọi $1 \\leq i \\leq n = 3$ nên chắc chắn bội số chung nhỏ nhất của các số này không thể chia hết cho $k = 5$.","points":2300.0,"partial":true,"time_limit":0.25,"memory_limit":1048576,"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}}