Fuel
Национална Олимпиада по Информатика 2011, Кръг 3
Time Limit: 0.5s, Memory Limit: 64MiB
Родителите на Елеонора са на мнението, че възпитанието на детето им е особено важно. С цел да не я разглезят и да я научат, че е хубаво човек сам да изкарва прехраната си, за 18-тия й рожден ден те и подариха чисто нова кола.

За максимално удовлетворение от новата си придобивка, Ели гледа да разнообразява пътя си до училище, и се чуди по колко различни начина може да стигне до там изминавайки минимален път. Можем да представим пътя й като права отсечка, по която има N различни точки - бензиностанциите, на които тя може да спира и презарежда. За съжаление родителите й не са избрали особено хубава кола (ще цитираме Ели: „Много бързо свършва резервоарът на пустия Вейрон!”) и не винаги е възможно тя да стигне от една точка до всяка друга.

Всеки интересен обект можем да бележим с разстоянието му в километри от началото на отсечката (където е нейният дом). Така домът й бива отбелязан с 0, училището с K, a с A1 < A2 < ... < AN – бензиностанциите. При пълен резервоар Ели може да измине L километра.

Нека например лимитът на резервоара L е 7, разстоянието К до училището е 10, и имаме три бензиностанции на съответно 3, 5 и 9 километра. Така Ели може да стигне до училище по 6 начина: (0, 3, 10), (0, 5, 10), (0, 3, 5, 10), (0, 3, 9, 10), (0, 5, 9, 10), (0, 3, 5, 9, 10). Забележете, че (0, 9, 10) е невъзможен път, защото разстоянието от 0 до 9 надхвърля лимита на резервоара, а (0, 5, 3, 10), е възможен, но не минимален път.
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N, K и L, разделени с интервали. На следващия ред ще има N числа Ai, отбелязващи разстоянията от началото на отсечката до всяка от бензиностанциите, сортирани във възходящ ред.
Изход
На стандартния изход за всеки тест изведете по едно единствено цяло число на отделен ред – броят начини, по които Ели може да стигне до училище. Тъй като този брой може да е особено голям, от вас се иска да изведете остатъка му по модул 1,000,000,007.
Ограничения
  • 1 ≤ N ≤ 1,000,000
  • 1 ≤ K ≤ 1,000,000,000
  • 1 ≤ L ≤ 1,000,000,000
  • 0 < Ai < Ai+1 < K
Примерен Вход Примерен Изход
3 10 7 3 5 9 6
5 13 7 1 2 3 4 5 0
42 66 13 1 3 4 5 7 9 10 11 14 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 44 46 47 48 49 51 53 54 56 57 58 59 60 61 62 64 65 188682339
Мрън!