Problem Description

Given non-negative integers $A$ and $B$, an ordered pair of non-negative integers $(x, y)$ is considered good if and only if:

• $0 \le x \le y$;
• $x + y = A$;
• $x \operatorname{AND} y = B$.

Here, $\operatorname{AND}$ represents the bitwise AND operation, denoted by the & operator in C++.

You need to find the sum of $y - x$ for all good ordered pairs $(x, y)$. Since this value can be very large, you only need to output the result modulo $M$.

Formally, you need to compute:

$$\left(\sum\limits_{x \ge 0}\sum\limits_{y \ge 0}\left(y - x\right)\left[\operatorname{good}(x, y)\right]\right)\bmod M$$

where $\operatorname{good}(x, y)$ is true if and only if the ordered pair $(x, y)$ is good.

Input Format

This problem contains multiple queries within a single test case.

The first line contains two integers $T$ and $M$, representing the number of queries and the modulus, respectively.

The next $T$ lines each contain two non-negative integers $A$ and $B$, representing a query.

Output Format

For each query, output a single integer on a new line, representing the answer modulo $M$.

Sample Input and Output

Sample Input #1

3 23
8 1
10 4
6 0

Sample Output #1

8
2
8

Sample Input #2

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

Sample Output #2

579
432
0
27
807
845

Sample Input #3

3 30996377
948664793464517468 401148893358688606
945266152577109588 398323527798785832
185133025738933982 77893802910442339

Sample Output #3

29793121
28589865
30695563

Sample Input #4

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

Sample Output #4

150959267
319548082
888288513
0
0

Notes/Hints

[Sample #1 Explanation]

For the first query, the good pairs are $(1, 7)$ and $(3, 5)$, so the answer is $(7 - 1) + (5 - 3) = 8$.

For the second query, the only good pair is $(4, 6)$, so the answer is $6 - 4 = 2$.

For the third query, the good pairs are $(0, 6)$ and $(2, 4)$, so the answer is $(6 - 0) + (4 - 2) = 8$.

[Sample #2 Explanation]

All queries satisfy the constraints of Subtask 1, and the last two queries also satisfy the constraints of Subtask 3.

Specifically, under the constraints of the third query, there are no good ordered pairs, so the answer is $0$.

[Sample #3 Explanation]

All queries satisfy the constraints of Subtask 2.

[Sample #4 Explanation]

All queries satisfy the constraints of Subtask 4.

Specifically, under the constraints of the fourth and fifth queries, there are no good ordered pairs, so the answer is $0$.

[Data Range]

This problem is bundled testing.

For $100\%$ of the data:

• $1 \le T \le 3 \times 10^5$;
• $0 \le A, B < 2^{60}$;
• $5 \le M \le 1.1 \times 10^9$;
• $M$ is a prime number.

The specific score distribution is as follows:

见题面 Input 部分

见题面 Output 部分