You are given an array $a$ of size $n$ and two integers $l$ and $r$. You have to find the number of partitions of array $a$ such that the sum of elements in each partition lies between $l$ and $r$(both inclusive). Since the answer can be large, find the answer modulo $10^9+7$ ($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.