atcoder#ARC141B. [ARC141B] Increasing Prefix XOR
[ARC141B] Increasing Prefix XOR
Score : points
Problem Statement
You are given positive integers and .
Find the number of sequences of positive integers that satisfy the following conditions, modulo .
- .
- , where .
Here, denotes bitwise .
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 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 4
5
For example, counts, since and where .
The other pairs that count are .
4 4
0
10 123456789
205695670