타냐, 공, 그리고 <<배타적 논리합>>

타냐는 공 $n$개를 가지고 있었고, $1$부터 $n$까지 번호를 붙였다. 하지만 안타깝게도 타냐는 모든 공을 강에 빠뜨렸고, 크게 낙담했다.

그녀를 위로하기 위해 오빠 세료자는 타냐에게 재미있는 수학 놀이를 제안했다. 공 번호들의 모든 쌍에 대한 배타적 논리합의 합을 구하는 것이다.

두 수의 배타적 논리합은 $\oplus$로 표기하며, 파스칼의 <<xor>> 연산이나 다른 언어의 <<\char 94>> 연산에 해당한다. 두 정수 $x \oplus y$를 계산하려면, 각 수를 이진법으로 나타내고, $i$번째 자리가 $x$와 $y$ 중 정확히 하나에서 $1$이면 결과의 $i$번째 자리를 $1$로 한다. 예를 들어, $3 \oplus 2 = 11_2 \oplus 10_2 = 1_2 = 1$, $17 \oplus 5 = 10001_2 \oplus 101_2 = 10100_2 = 20$이다.

타냐를 도와주자! 그녀의 공 번호들의 모든 쌍에 대한 배타적 논리합의 합을 구하라. 타냐는 큰 수를 좋아하지 않으므로, 답은 $10^9 + 7$로 나눈 나머지를 출력해야 한다.

예를 들어, 타냐가 공 $3$개를 가지고 있었다면, 구하는 값은 $(1 \oplus 2) + (1 \oplus 3) + (2 \oplus 3) = 3 + 2 + 1 = 6$이다.

첫째 줄에 수 $n$이 주어진다. $n$은 타냐가 가진 공의 개수이다 ($1 \le n \le 10^9$).

그녀의 공 번호들의 모든 쌍에 대한 배타적 논리합의 합을 $10^9 + 7$로 나눈 나머지를 출력한다.