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 .
For all subtasks:
Subtask 1 [10%]
Subtask 2 [30%]
Subtask 3 [60%]
No additional constraints.
You will receive one line of input containing the positive integer .
Output the number of strategic subsequences, modulo .
The strategic subsequences of are: