Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Magical Pascal

Limits: 2s, 512 MB

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

InputOutput
3
1
5
4

Explanation

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.

Discussion
Submit

Login to submit