Problem Statement

Let's define a function as calculateValue(X) for all X>0 as follows:
• Write the number X in base 10 representation • Split the number X into contiguous subsequences such that the number subsequences and each subsequence is made up of identical digits

• For each subsequence, Let's say that the most significant digit it contains is the i-th digit, where i=0 corresponds to the least significant digit of X.

For example, if X = 12233322211 can be split into the following subsequences - "1", "22", "333", "222", "11", where i = 7 for the sequence "333" and i = 1 for
the subsequence "11"

• The value for each subsequence can be calculated as d x 10^i, where d is the digit repeated in the
sequence

• calculateValues(X) is calculated as the sum of all these values.

For example, calculateValues(12233322211) = 1 x 10^10 + 2 x 10^9 +3 x 10^7 + 2 x 10^4 + 1 x 10^1

We have two numbers low and high with Now and Nhigh digits respectively (without leading zeros). You need to calculate finalAnswer as the sum of calculateValues(X) for each X between low and high inclusive.

Since this number can be very large, give you answer module 10⁹ + 7.

Input Format

• The first line contains two space separated integers, Now and low respectively.
• The second line contains two space separated integers, Nhigh and high respectively.

Both low and high do no contain leading zeros

Output Format

• Print a single line containing one integer - finalAnswer

Constraints

• 1 <= low <= high 10^1000000
• 1 <= Now, Nhigh <= 10^6

Sample Test Case

Sample Input 1

18 2 12

Sample Output 1

9 49

Explanation

In this case, we have low = 8 and high = 12, now,

calculateValues(8) = 8 x 10^0 = 8
calculateValues(9) = 9 x 10^0 = 9
calculateValues(10) = 1 x 10 ^ 1+ 0 x 10^0 = 10
calculateValues(11) = 1 x 10^1 = 10
calculateValues(12) = 1 x 10^1 + 2 x 10^0 = 12

So our result comes out to be 8 + 9 + 10 + 10 + 12 = 49