Submit solution

Points:
15 (partial)

Time limit:
1.0s

Memory limit:
128M

Authors:

Problem type

Allowed languages

Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, ~~CommonLisp~~, D, Dart, F#, Forth, Fortran, Go, ~~Groovy~~, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, ~~Nim~~, ~~ObjC~~, OCaml, ~~Octave~~, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 .

#### Constraints

For all subtasks:

##### Subtask 1 [10%]

##### Subtask 2 [30%]

##### Subtask 3 [60%]

No additional constraints.

#### 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:

## Comments