[ARC133D] Range XOR
Score : points
Problem Statement
Given are integers , , and . Find the number of pairs of integers that satisfy both of the conditions below, modulo .
Here, denotes the bitwise operation.
What is bitwise $\mathrm{XOR}$?
The bitwise $\mathrm{XOR}$ of non-negative integers $A$ and $B$, $A \oplus B$, is defined as follows:
- When $A \oplus B$ is written in base two, the digit in the $2^k$'s place ($k \geq 0$) is $1$ if exactly one of $A$ and $B$ is $1$, and $0$ otherwise.
Generally, the bitwise \mathrm{XOR} of k integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k). We can prove that this value does not depend on the order of p_1, p_2, p_3, \dots p_k.
Constraints
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
Output
Print the answer.
1 3 3
2
The two pairs satisfying the conditions are and .
10 20 0
6
1 1 1
1
12345 56789 34567
16950