## CCO Preparation Test 2 - Subsets

View as PDF

Points: 25 (partial)
Time limit: 0.6s
Memory limit: 128M

Author:
Problem types

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