[ARC156D] Xor Sum 5
Score : points
Problem Statement
You are given a sequence of non-negative integers and a positive integer .
Find the bitwise of over all sequences of positive integer sequences such that .
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 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 the input are integers.
Input
The input is given from Standard Input in the following format:
Output
Print the answer.
2 2
10 30
40
There are four sequences to consider: , for which is , respectively. Thus, the answer is .
4 10
0 0 0 0
0
11 998244353
314 159 265 358 979 323 846 264 338 327 950
236500026047