#agc009c. [agc009_c]Division into Two
[agc009_c]Division into Two
Problem Statement
There is a set consisting of distinct integers. The -th smallest element in this set is . We want to divide this set into two sets, and , such that:
- The absolute difference of any two distinct elements in is or greater.
- The absolute difference of any two distinct elements in is or greater.
How many ways are there to perform such division, modulo ? Note that one of and may be empty.
Constraints
- All input values are integers.
Input
The input is given from Standard Input in the following format:
:
Output
Print the number of the different divisions under the conditions, modulo .
Sample Input 1
Sample Output 1
There are five ways to perform division:
- {}, {}
- {}, {}
- {}, {}
- {}, {}
- {}, {}