KBTU OPEN 2014 Spring

Contest preparation

One time Arti was asked to prepare several programming contests. As he is very lazy, he decided to cheat a little. He prepared n tasks and for i-th task he prepared si statements. Now he wants to gather contests from these tasks with following rules:

  • each task can be used in a contest only once;
  • a contest must consist of a to b tasks;
  • two contests are different if there is at least one task that is in one contest and not in the second one or if there is at least one task that has different statements in these contests;
  • only set of tasks matters, not the order.

Calculate, how many different contest Arti can prepare. As this number can be very large, output it modulo 109 + 7.


First line contains n, a, b (1abn10000). Second line contains n integer numbers si (1si100).


Print one line - the number of different contests Arti can prepare modulo 109 + 7.

Time limit 1 second
Memory limit 128 MiB
Input example #1
2 1 2
3 4
Output example #1
Source 2014 KBTU Open, Spring Kazakhstan, Almaty, April 20, Problem I