[ARC146C] Even XOR
Score : points
Problem Statement
How many sets consisting of non-negative integers between and (inclusive) satisfy the following condition? Print the count modulo .
- Every non-empty subset of satisfies at least one of the following:- The number of elements in is odd.
- The of the elements in is not zero.
- The number of elements in is odd.
- The of the elements in is not zero.
What is $\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 the digits in that place of $A$ and $B$ is $1$, and $0$ otherwise.
Generally, the bitwise \mathrm{XOR} of k non-negative 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.
2
15
Sets such as , , and satisfy the condition.
On the other hand, does not.
This is because the subset of has an even number of elements, whose bitwise is .
146
743874490