Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3412
Special Special Judge II

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Because of recent update of ZOJ, some special judges were broken. You're requested to fix the special judge for Problem 1000.

The input of Problem 1000 contains n positive integers, a0, a1...an-1. And the output should contain n positive integers, b0, b1...bn-1. All bi (i=0, 1...n-1) should be in the range [x, y]. Let di be the greatest common divisor of ai and bi. If the sum of di(i=0, 1, 2, ..., n-1) is in the range [s, t], the answer is acceptable.

The special judge for Problem 1000 has already been done, but you still want to known how many different outputs will be accepted by the special judge.

Input

There are multiple cases, processing to the end of file.

The first line of input contains 5 integers, n, s, t, x, y (1 ≤ n ≤ 40, 1 ≤ s ≤ t ≤ 3000, 1≤ x ≤ y ≤ 109).

The following line contains n positive integers, a0,a1...an-1.(2 ≤ ai ≤ 106).

Output

One line contains the number of acceptable answers, the result might be very large, just print it mod 1000000007.

Sample Input

4 10 20 20 30
48 22 23 6

Sample Output

2650

Author: CHEN, Zhangyi
Contest: ZOJ Monthly, October 2010
Submit    Status