{"code":"binarysearch","name":"Tìm kiếm nhị phân?","description":"Cho hai số nguyên $n$ và $x$. Hãy đếm số lượng dãy $a$ độ dài $n$, mỗi phần tử có giá trị trong khoảng $[1, n]$ và hàm sau có giá trị đúng:\r\n\r\n```\r\nbinary_search(a, n, x)\r\n left = 1\r\n right = n\r\n while left <= right\r\n middle = (left + right) / 2\r\n if a[middle] == x then\r\n return true\r\n \r\n if a[middle] < x then\r\n left = middle + 1\r\n else\r\n right = middle - 1\r\n \r\n return false\r\n```\r\n\r\nLưu ý rằng các phần tử của dãy được đánh chỉ số từ $1$ và phép chia được thực hiện ở phần nguyên (làm tròn xuống).\r\n\r\n

Input

\r\n\r\n- Một dòng duy nhất chứa hai số nguyên $n$ và $x$ ($1 \\leq x \\leq n \\leq 10 ^ {12}$).\r\n\r\n

Output

\r\n\r\n- Một dòng duy nhất chứa một số nguyên là số lượng dãy $a$ thỏa mãn sau khi chia lấy dư cho $10 ^ 9 + 7$.\r\n\r\n

Scoring

\r\n\r\n- Subtask 1 (20% số điểm): $n \\leq 7$.\r\n- Subtask 2 (20% số điểm): $n \\leq 10 ^ 3$.\r\n- Subtask 3 (30% số điểm): $n \\leq 10 ^ 6$.\r\n- Subtask 4 (30% số đ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\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 3 2\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 15\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n Các dãy thỏa mãn là: $[1, 1, 2]$, $[1, 2, 1]$, $[1, 2, 2]$, $[1, 2, 3]$, $[2, 1, 2]$, $[2, 2, 1]$, $[2, 2, 2]$, $[2, 2, 3]$, $[2, 3, 1]$, $[2, 3, 2]$, $[2, 3, 3]$, $[3, 1, 2]$, $[3, 2, 1]$, $[3, 2, 2]$ và $[3, 2, 3]$.","points":1800.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}}