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.