Informatica Online Judge

  Sum of different corresponding bits for all pairs [1772 / 06EC]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 26   Total Tried : 191


The Champion of this Problem (C++) : kdh9949 - ms / 405byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]

Background

$f(x, y)$를 두 정수 $x, y$의 이진 표현에서 같은 위치의 비트가 서로 다른 수를 출력하는 함수로 정의한다.

즉, $f(2, 7) = 2$가 된다. $2 = 010, 7 = 111$ 가 되며 첫 번째와 세번째 비트가 서로 다르므로 결과는 $2$가 된다.

$N$개의 정수가 주어 질 때 $(i, j) 1 <= i, j <= N$ 인 모든 쌍에 대하여 $f(Ai, Aj)$의 합을 출력하시오.

Input

첫 번째 줄에 정수의 개수를 나타내는 $N$이 입력된다.

두 번째 줄 부터 $N$개의 정수 $A[i]$가 입력된다

$[입력값의 정의역]$

$1≤ N ≤ 100,000$
$1≤ A[i] ≤ 100,000$

Output

$N$개의 정수가 주어 질 때 $(i, j) 1 <= i, j <= N$ 인 모든 쌍에 대하여 $f(Ai, Aj)$의 합을 $1,000,000,007$로 나눈 나머지를 출력한다.

IO Example

입력1
3
1 3 5

출력1
8

설명1:
$[f(1, 1) + f(1, 3) + f(1, 5)] + [f(3, 1) + f(3, 3) + f(3, 5)] + [f(5, 1) + f(5, 3) + f(5, 5)] =$

$(0 + 1 + 1) + (1 + 0 + 2) + (1 + 2 + 0) = 8$

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]