Submit solution

Points:
25 (partial)

Time limit:
0.6s

Memory limit:
128M

Author:

Problem types

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

When Bruce learned set theory, he assigned a homework question to his students.

Given a positive integer , find the number of subsets of the whole set that satisfies the following constraint: if an integer is in the subset, then the integers and are **not** in the subset. For example, given , the whole set is . The number of subsets satisfying the constraint is , including the empty set: , , , , , , , and .

#### Input Specification

The input will consist of one integer .

#### Output Specification

Output the number of subsets that satisfy the above constraints mod .

#### Sample Input

`4`

#### Sample Output

`8`

## Comments