
ZOJ Problem Set  3412
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, a_{0}, a_{1}...a_{n1}. And the output should contain n positive integers, b_{0}, b_{1}...b_{n1}. All b_{i} (i=0, 1...n1) should be in the range [x, y]. Let d_{i} be the greatest common divisor of a_{i} and b_{i}. If the sum of d_{i}(i=0, 1, 2, ..., n1) 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. InputThere 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 ≤ 10^{9}). The following line contains n positive integers, a_{0},a_{1}...a_{n1}.(2 ≤ a_{i} ≤ 10^{6}). OutputOne line contains the number of acceptable answers, the result might be very large, just print it mod 1000000007. Sample Input4 10 20 20 30 48 22 23 6 Sample Output2650 Author: CHEN, Zhangyi Contest: ZOJ Monthly, October 2010 