## A Math Contest P5 - Good Arrays

View as PDF

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types

For each integer , a good array is a non-empty array which satisfies the following conditions:

1. Every element in the array is between the array's size and , inclusive.
2. The array is strictly increasing.
3. There are no two consecutive integers in the array.

Given an integer , determine the number of good arrays.

#### Input Specification

The only line contains an integer, .

#### Output Specification

Output the number of good arrays modulo .

#### Sample Input

4

#### Sample Output

5

#### Explanation for Sample

The good arrays are

Every array is strictly increasing, has elements between the array size and , and contains no consecutive integers ().