Strategic Arrays

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 128M

Authors:
Problem type

For any 1-indexed array of consecutive positive integers [1, 2, 3,..N] a subsequence [a_{1}, a_{2}, ... 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, 3,..N], modulo 10^{9}+7.

Constraints

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

Subtask 1 [10%]

1 \leq N \leq 15

Subtask 2 [30%]

1 \leq N \leq 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]


Comments

There are no comments at the moment.