Problem Background

SY has finally tidied up her messy bed and just arrived in the classroom when she received a note from QM.

To: Dear SY

    Look at the equation I dreamed of last night. Solve it and I'll give you candy.

From: Your QM.

SY naturally couldn't resist the temptation of $C_{6}H_{12}O_{6}$, but she was dumbfounded when she saw the elaborate equation on the back of the note. However, SY really wants the candy.

Problem Description

Calculate the result of:

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

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

Input Format

A single line containing an integer n.

Output Format

A single line containing an integer, the answer modulo $10^9+7$.

Sample Input and Output

Sample Input #1

2

Sample Output #1

5

Sample Input #2

5

Sample Output #2

447

Notes

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

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

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

见题面 Input 部分

见题面 Output 部分