Consider a full binary tree of height h, and $2^h - 1$ nodes. The tree is rooted at node 1, and any internal node i has 2 children numbered $2i$ and $2i+1$. Define $g(i,j)$ as the greatest common divisor of all the nodes which lie on the simple path from node i to node j.

You are given h. Find the value of $\displaystyle \sum_{1 \le i \le j \lt 2^h} g(i,j)$. Since this value might be very big, print it modulo 10^9 + 7

Input
The first line contains h, the height of the tree

Output
Print one line containing the required value.

Constraints
$1 \le h \le 10^{18}$