#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
5 3 7
1
3
6
9
12
Sample Output 1
5
There are five ways to perform division:
- {}, {}
- {}, {}
- {}, {}
- {}, {}
- {}, {}
Sample Input 2
7 5 3
0
2
4
7
8
11
15
Sample Output 2
4
Sample Input 3
8 2 9
3
4
5
13
15
22
26
32
Sample Output 3
13
Sample Input 4
3 3 4
5
6
7
Sample Output 4
0