题目描述

给定非负整数 $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$
4	无特殊限制	$35$