For each integer , a good array is a non-empty array which satisfies the following conditions:
- Every element in the array is between the array's size and , inclusive.
- The array is strictly increasing.
- There are no two consecutive integers in the array.
Given an integer , determine the number of good arrays.
Subtask 1 [10%]
Subtask 2 [10%]
Subtask 3 [80%]
No additional constraints.
The only line contains an integer, .
Output the number of good arrays modulo .
Explanation for Sample
The good arrays are
Every array is strictly increasing, has elements between the array size and , and contains no consecutive integers ().