Strategic Arrays

View as PDF

Submit solution

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

Problem type

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.


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


Sample Output



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


There are no comments at the moment.