Description

Find the value of

$$\sum_{i=1}^{2^{n}}\log_{2}{(\prod_{j = 1}^{i}lowbit(j))}$$

where $lowbit(x)$ means the result of x&(~x+1).

Input Format

One line containing an integer $n$.

Output Format

One line containing one integer, the answer modulo $10^9+7$.

2

5

5

447

Hint

For the first $20\%$ of the testdata, $1 \leq n \leq 60$.

For the first $50\%$ of the testdata, $1 \leq n \leq 10^4$.

For the full $100\%$ of the testdata, $1 \leq n \leq 2^{62}$.

Translated by ChatGPT 5