There is fence which consists of $n$ wooden blocks with each block having a number written on it represented by an array $a$. The painter is also given two numbers $l$ and $r$ . He is given the task to paint the fence using at most $n$ colors. But there are certain conditions which the painter must follow while painting:

• He has to paint the fence in sequential manner from left to right i.e, first paint the first block then second block and so on without leaving any block not being painted. 
• He will also use colors in sequential manner i.e, first paint with 1st color,then with 2nd color and so on. Note that he can paint any number of blocks sequentially with a single color and a color once used cannot be reused.
• The sum of numbers written on blocks painted with same color must lie between $l$ and $r$ ( both inclusive ).

    The painter wants to know in how many ways can he paint the fence.Since the answer can be large, find the answer modulo $1000000007$.

Input Format

First line contains 3 space separated denoting the values of $n$, $l$ and $r$ $(1 \le n \le 10^5,1 \le l \le r \le 10^{12})$,

Next line contains $n$ space separated integers denoting the values of array $a$ $(1 \le a[i] \le r)$.

Output Format

Print the answer in a single line.