Segment Tree Cover Expectation

Little L adores the segment tree, a data structure that can very efficiently solve many practical problems. He builds a segment tree on the interval \([1, n]\) as follows:

• The initial tree has a single node covering \([1, n]\).
• For a node covering \([L, R]\) with \(L < R\), let \(mid = \left\lfloor \frac{L+R}{2} \right\rfloor\). He then creates two children covering \([L, mid]\) and \([mid+1, R]\) respectively.

Define a function \(cover(a, b)\) for \(1 \le a \le b \le n\) as the minimum number of nodes from the segment tree that perfectly cover the interval \([a, b]\) (that is, the chosen nodes do not overlap and their union is exactly \([a, b]\); moreover, a node is chosen only if its parent’s interval is not completely contained in \([a, b]\)).

Notice that every sub‐interval \([a, b]\) of \([1, n]\) (there are \(\frac{n(n+1)}{2}\) many) has a unique minimal cover in the segment tree. Little L wants to roughly evaluate the performance of his segment tree. To do so, he randomly (with equal probability) picks a sub‐interval \([A, B]\) among all \(\frac{n(n+1)}{2}\) sub‐intervals, and he uses \(cover(A, B)\) as a performance measure.

Your task is to compute

[ S = \left(\mathbb{E}[cover(A,B)] \times \frac{n(n+1)}{2}\right) \mod 1{,}000{,}000{,}007. ]

It can be shown that \(S\) is always an integer. Equivalently, if you let \(S\) be the sum of \(cover(a, b)\) over all sub‐intervals \([a, b]\) of \([1, n]\), then compute \(S \mod 1{,}000{,}000{,}007\).

Input Format: A single positive integer \(n\).

Output Format: Output the integer \(S \mod 1{,}000{,}000{,}007\).

Note: The segment tree is built recursively exactly as described. A node representing \([L,R]\) is used in the covering of \([a,b]\) if and only if \([L,R] \subseteq [a, b]\) and either the node is the root or its parent (covering \([L_p,R_p]\)) is not completely contained in \([a,b]\); that is, at least one of \(a > L_p\) or \(b < R_p\) holds.

inputFormat

The input consists of a single integer \(n\) (\(1 \le n \le \text{upper bound}\)).

For example:

5

outputFormat

Output a single integer: the value of \(S\) modulo \(1{,}000{,}000{,}007\).

For the sample input above, the correct output is 23.

sample

1

1