XOR Sum in Interval

Given a positive integer n, compute the following sum modulo \(10^9+7\):

\[ S = \sum_{i=1}^{n} \sum_{j=1}^{n} \; \bigl[\, i \oplus j \in [\min(i,j),\max(i,j)]\bigr] \cdot (i \oplus j), \]

In other words, for every pair of integers \(i, j\) with \(1 \le i,j \le n\), if the bitwise XOR of \(i\) and \(j\), denoted by \(i \oplus j\), lies in the closed interval \([\min(i,j),\max(i,j)]\), then add \(i \oplus j\) to the sum; otherwise, ignore the pair. Since the answer may be very large, output the result modulo \(10^9+7\).

inputFormat

The input consists of a single line containing one integer n (\(1 \le n\le N\)).

outputFormat

Output a single integer, the value of \(S\) modulo \(10^9+7\).

sample

1

0