Score : 1100 points
There is a set consisting of N distinct integers. The i-th smallest element in this set is S_i. We want to divide this set into two sets, X and Y, such that:
How many ways are there to perform such division, modulo 10^9 + 7? Note that one of X and Y may be empty.
The input is given from Standard Input in the following format:
N A B S_1 : S_N
Print the number of the different divisions under the conditions, modulo 10^9 + 7.
5 3 7 1 3 6 9 12
5
There are five ways to perform division:
7 5 3 0 2 4 7 8 11 15
4
8 2 9 3 4 5 13 15 22 26 32
13
3 3 4 5 6 7
0