Background

SY finally tidied up her messy quilt. As soon as she arrived in the classroom, she received a note from QM...

To: Dear SY

    Take a look at the formula I dreamed of last night. Solve it and I will give you candy.

From: Your QM.

SY, of course, could not resist the temptation of $C_{6}H_{12}O_{6}$. But when she saw the fancy formula on the back of the note, she was stunned... Still, SY really wanted to eat candy.

Problem 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