Magical Pascal

Given an integer $N$, find the number of elements which are even in the first $N$ rows of the Pascal's triangle. If you have forgotten, we have attached an image below which shows the first 11 rows of the Pascal's triangle.

The rows of Pascal's triangle are conventionally enumerated starting with row $M = 0$ at the top (the 0-th row). The entries in each row are numbered from the left beginning with $K = 0$. So the $M$-th row of the pascal triangle consists of exactly $M+1$ elements. And for each $K$ ($0 \leq K \leq M$), the $K$-th element of the $M$-th row is basically $\binom{M}{K}$ from left to right.

Input

The only line of the input contains a single integer $N$ ($1 \leq N \leq 10^{18}$).

Output

Print a single integer, the number of elements which are even in the first $N$ rows of Pascal's triangle. As the answer can be very large, compute it modulo ${10^9+7}$.

Samples

Input	Output
3	1
In the first sample case, number of even elements in the first three rows are respectively 0, 0 and 1. Hence the answer is $(0+0+1) = 1$.

Input	Output
5	4