High School Programming League Problems Archive

For given integers a and b your task is to find how many integers in the range [a,b] are divisible by a number x, and have the additional property that the sum of their digits lies in the range [l,r] for given l,r.

Input

In the first line you're given a and b ( 1 <= a <= b < 10^100 ).
In the second line you're given three positive integers x ( 1 <= x <= 10 ), l, r ( 1 <= l <= r <= 1,000 ).

Output

In the first and only line output the result modulo 1,000,000,007.

Example

Input:
1 100
5 10 50

Output:
5

Scoring

By solving this problem you score 10 points.