『STA - R4』And

给定非负整数 $A, B$，定义有序非负整数对 $(x, y)$ 为好的当且仅当： - $0 \le x \le y$； - $x + y = A$； - $x \operatorname{AND} y = B$。 其中 $\operatorname{AND}$ 代表按位与运算。在 C++ 语言中由 `&` 运算符表示。 你需要求出所有好的有序非负整数对 $(x, y)$ 的 $y - x$ 的和。 由于该值可能很大，你只需要输出其对 $M$ 取模后的结果。 形式化的，你需要求出 $$\left(\sum\limits_{x \ge 0}\sum\limits_{y \ge 0}\left(y - x\right)\left[\operatorname{good}(x, y)\right]\right)\bmod M$$ 其中 $\operatorname{good}(x, y)$ 为真与有序非负整数对 $(x, y)$ 为好的等价。

**本题单个测试点内含有多组询问。** 第一行两个整数 $T, M$，分别代表询问组数和模数。 接下来 $T$ 行，每行两个非负整数 $A, B$，代表一组询问。

对于每组测试数据，输出一行一个整数，代表答案。

3 23
8 1
10 4
6 0

8
2
8

6 883
196483 132
330788 4353
137168 35030
615316 264202
387442 0
407154 0

579
432
0
27
807
845

3 30996377
948664793464517468 401148893358688606
945266152577109588 398323527798785832
185133025738933982 77893802910442339

29793121
28589865
30695563

5 992362009
248232552654965455 563160474979616
553521216364206023 14357560845404368
668113789984338832 146840018434951169
620025528908068087 506797735136774536
522926854352266209 860580850297773973

150959267
319548082
888288513
0
0

**【样例 #1 解释】** 对于第一组询问，好的数对有 $\left(1, 7\right)$ 和 $\left(3, 5\right)$，因此答案为 $\left(7 - 1\right) + \left(5 - 3\right) = 8$。 对于第二组询问，好的数对只有 $\left(4, 6\right)$，因此答案为 $6 - 4 = 2$。 对于第三组询问，好的数对有 $\left(0, 6\right)$ 和 $\left(2, 4\right)$，因此答案为 $\left(6 - 0\right) + \left(4 - 2\right) = 8$。 **【样例 #2 解释】** 其所有询问均满足子任务 1 的限制，且后两组询问同时满足子任务 3 的限制。 特别的，在第三组询问的限制下，不存在好的有序非负整数对，因此答案为 $0$。 **【样例 #3 解释】** 其所有询问均满足子任务 2 的限制。 **【样例 #4 解释】** 其所有询问均满足子任务 4 的限制。 特别的，在第四、五组询问的限制下，不存在好的有序非负整数对，因此答案为 $0$。 **【数据范围】** **本题采用捆绑测试。** 对于 $100\%$ 的数据： - $1 \le T \le 3 \times 10^5$； - $0 \le A, B < 2^{60}$； - $5 \le M \le 1.1 \times 10^9$； - $M$ 为质数。 具体部分分分配如下： |Subtask 编号|数据范围|分值| |:--------:|:--------:|:--------:| |1|$T \le 200, 0 \le A, B \le 8 \times 10^5$|$15$| |2|对于每组询问，好的数对个数不超过 $1000$ 个|$25$| |3|$B = 0$|$25$| |4|无特殊限制|$35$|