# 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

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 |

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.

#### flash_7

Tarango works NSUPS. He loves to play FIFA & travel with friends. When not solving problems, he spends most of his time day dreaming. And, he most definitely is not a "manga lover". →