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]~