## Strategic Arrays

View as PDF

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

Authors:
Problem type

For any 1-indexed array of consecutive positive integers a subsequence 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 , print the number of strategic subsequences of , modulo .

#### Input Specification

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

#### Output Specification

Output the number of strategic subsequences, modulo .

#### Sample Input

4

#### Sample Output

7

#### Explanation

The strategic subsequences of are: