100 atcoder#ABC147D. [ABC147D] Xor Sum 4
[ABC147D] Xor Sum 4
Score : points
Problem Statement
We have integers. The -th integer is .
Find $\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} (A_i \text{ XOR } A_j)$, modulo .
What is $\text{ XOR }$?
The XOR of integers and , , is defined as follows:
- When is written in base two, the digit in the 's place () is if either or , but not both, has in the 's place, and otherwise.
For example, . (In base two: .)
Constraints
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
Output
Print the value $\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} (A_i \text{ XOR } A_j)$, modulo .
3
1 2 3
6
We have $(1\text{ XOR } 2)+(1\text{ XOR } 3)+(2\text{ XOR } 3)=3+2+1=6$.
10
3 1 4 1 5 9 2 6 5 3
237
10
3 14 159 2653 58979 323846 2643383 27950288 419716939 9375105820
103715602
Print the sum modulo .