{"raw_statement":[{"iden":"statement","content":"给定非负整数 $A, B$，定义有序非负整数对 $(x, y)$ 为好的当且仅当：\n\n- $0 \\le x \\le y$；\n- $x + y = A$；\n- $x \\operatorname{AND} y = B$。\n\n其中 $\\operatorname{AND}$ 代表按位与运算。在 C++ 语言中由 `&` 运算符表示。\n\n你需要求出所有好的有序非负整数对 $(x, y)$ 的 $y - x$ 的和。\n\n由于该值可能很大，你只需要输出其对 $M$ 取模后的结果。\n\n形式化的，你需要求出\n\n$$\\left(\\sum\\limits_{x \\ge 0}\\sum\\limits_{y \\ge 0}\\left(y - x\\right)\\left[\\operatorname{good}(x, y)\\right]\\right)\\bmod M$$\n\n其中 $\\operatorname{good}(x, y)$ 为真与有序非负整数对 $(x, y)$ 为好的等价。"},{"iden":"input","content":"**本题单个测试点内含有多组询问。**\n\n第一行两个整数 $T, M$，分别代表询问组数和模数。\n\n接下来 $T$ 行，每行两个非负整数 $A, B$，代表一组询问。"},{"iden":"output","content":"对于每组测试数据，输出一行一个整数，代表答案。"},{"iden":"note","content":"**【样例 #1 解释】**\n\n对于第一组询问，好的数对有 $\\left(1, 7\\right)$ 和 $\\left(3, 5\\right)$，因此答案为 $\\left(7 - 1\\right) + \\left(5 - 3\\right) = 8$。\n\n对于第二组询问，好的数对只有 $\\left(4, 6\\right)$，因此答案为 $6 - 4 = 2$。\n\n对于第三组询问，好的数对有 $\\left(0, 6\\right)$ 和 $\\left(2, 4\\right)$，因此答案为 $\\left(6 - 0\\right) + \\left(4 - 2\\right) = 8$。\n\n**【样例 #2 解释】**\n\n其所有询问均满足子任务 1 的限制，且后两组询问同时满足子任务 3 的限制。\n\n特别的，在第三组询问的限制下，不存在好的有序非负整数对，因此答案为 $0$。\n\n**【样例 #3 解释】**\n\n其所有询问均满足子任务 2 的限制。\n\n**【样例 #4 解释】**\n\n其所有询问均满足子任务 4 的限制。\n\n特别的，在第四、五组询问的限制下，不存在好的有序非负整数对，因此答案为 $0$。\n\n**【数据范围】**\n\n**本题采用捆绑测试。**\n\n对于 $100\\%$ 的数据：\n\n- $1 \\le T \\le 3 \\times 10^5$；\n- $0 \\le A, B < 2^{60}$；\n- $5 \\le M \\le 1.1 \\times 10^9$；\n- $M$ 为质数。\n\n具体部分分分配如下：\n\n|Subtask 编号|数据范围|分值|\n|:--------:|:--------:|:--------:|\n|1|$T \\le 200, 0 \\le A, B \\le 8 \\times 10^5$|$15$|\n|2|对于每组询问，好的数对个数不超过 $1000$ 个|$25$|\n|3|$B = 0$|$25$|\n|4|无特殊限制|$35$|"}],"translated_statement":null,"sample_group":[["3 23\n8 1\n10 4\n6 0\n","8\n2\n8\n"],["6 883\n196483 132\n330788 4353\n137168 35030\n615316 264202\n387442 0\n407154 0\n","579\n432\n0\n27\n807\n845\n"],["3 30996377\n948664793464517468 401148893358688606\n945266152577109588 398323527798785832\n185133025738933982 77893802910442339\n","29793121\n28589865\n30695563\n"],["5 992362009\n248232552654965455 563160474979616\n553521216364206023 14357560845404368\n668113789984338832 146840018434951169\n620025528908068087 506797735136774536\n522926854352266209 860580850297773973\n","150959267\n319548082\n888288513\n0\n0\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}