For any 1-indexed array of consecutive positive integers $[1,2,\dots ,N]$ a subsequence $[a_1,a_2,\dots ,a_k]$ constructed from the first array is considered strategic if every term with an odd index in the subsequence is odd and every term with an even index is even.

A subsequence is a sequence which is derived from the original sequence by deleting zero or more elements without changing the order of the remaining elements.

Given an integer $N$, print the number of strategic subsequences of $[1,2,\dots ,N]$, modulo ${10}^9+7$.

Constraints

For all subtasks: $1\le N\le {10}^{18}$

Subtask 1 [10%]

$1\le N\le 15$

Subtask 2 [30%]

$1\le N\le {10}^6$

Subtask 3 [60%]

No additional constraints.

Input Specification

You will receive one line of input containing the positive integer $N$.

Output Specification

Output the number of strategic subsequences, modulo ${10}^9+7$.

Sample Input

4

Sample Output

7

Explanation

The strategic subsequences of $[1,2,3,4]$ are: $[1],[3],[1,2],[1,4],[3,4],[1,2,3],[1,2,3,4]$