E - スムーズな山道 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 433 点

問題文

高橋君は登山が趣味で、山道の「なめらかさ」に興味を持っています。

高橋君は山道を正の整数で表現します。正の整数 X の十進表記が k 桁であるとし、最上位桁（左端）から順に各桁の数字を d_1, d_2, \ldots, d_k とします。高橋君はこれらの数字を、左から右へ一列に並んだ k 個の地点の標高レベルと見なしています。すなわち、第 i 地点の標高レベルは d_i（0 以上 9 以下の整数）です。ただし X は先頭に余分な 0 を含まない正の整数であるため、d_1 は 1 以上 9 以下です。

このとき、隣接する2地点間の標高差を順に並べた列

e_1, e_2, \ldots, e_{k-1} \quad \text{ただし} \quad e_i = |d_i - d_{i+1}| \quad (1 \leq i \leq k-1)

を「X の段差列」と呼びます。k = 1（X が1桁の数）のとき、段差列は空列です。

高橋君は、段差列が単調非減少である正の整数を「スムーズな山道」と呼んでいます。ここで単調非減少とは、すべての 1 \leq i \leq k-2 に対して e_i \leq e_{i+1} が成り立つことをいいます。直感的には、歩き始めは段差が小さく、進むにつれて段差が大きくなっても構わないが、途中で段差が小さくなることがない山道です。X が1桁の数（段差列が空列）または2桁の数（段差列の要素が1つだけ）の場合は、条件を満たすべき i が存在しないため、常にスムーズな山道です。

例：

  • X = 1234 の段差列は (|1-2|,\ |2-3|,\ |3-4|) = (1, 1, 1) です。1 \leq 1 \leq 1 と単調非減少なので、スムーズな山道です。
  • X = 3152 の段差列は (|3-1|,\ |1-5|,\ |5-2|) = (2, 4, 3) です。4 > 3 となる箇所があるため、スムーズな山道ではありません。

正の整数 L と R が与えられます。L 以上 R 以下の整数のうち、スムーズな山道であるものの個数を 10^9 + 7 で割った余りを求めてください。

制約

  • 1 \leq L \leq R < 10^{5000}
  • L および R は先頭に余分な 0 を含まない十進表記で与えられる。したがって、L の桁数および R の桁数はいずれも 5000 以下である。

入力

L
R
  • 1 行目には、範囲の下限を表す正の整数 L が十進表記で与えられる。
  • 2 行目には、範囲の上限を表す正の整数 R が十進表記で与えられる。

出力

L 以上 R 以下のスムーズな山道の個数を 10^9 + 7 で割った余りを1行で出力せよ。

入力例 1

1
20

出力例 1

20

入力例 2

98
123

出力例 2

24

入力例 3

1000
50000

出力例 3

6624

入力例 4

123456789012345678901234567890
987654321098765432109876543210

出力例 4

426844825

入力例 5

1
1

出力例 5

1

Score : 433 pts

Problem Statement

Takahashi enjoys mountain climbing as a hobby and is interested in the "smoothness" of mountain paths.

Takahashi represents mountain paths as positive integers. Let the decimal representation of a positive integer X have k digits, and let the digits from the most significant digit (leftmost) to the least significant be d_1, d_2, \ldots, d_k. Takahashi regards these digits as elevation levels of k points arranged in a row from left to right. That is, the elevation level of the i-th point is d_i (an integer between 0 and 9, inclusive). Since X is a positive integer without leading zeros, d_1 is between 1 and 9, inclusive.

The sequence of elevation differences between adjacent points, listed in order,

e_1, e_2, \ldots, e_{k-1} \quad \text{where} \quad e_i = |d_i - d_{i+1}| \quad (1 \leq i \leq k-1)

is called the "step sequence of X". When k = 1 (i.e., X is a single-digit number), the step sequence is an empty sequence.

Takahashi calls a positive integer whose step sequence is monotonically non-decreasing a "smooth mountain path." Here, monotonically non-decreasing means that e_i \leq e_{i+1} holds for all 1 \leq i \leq k-2. Intuitively, this is a mountain path where the steps are small at the beginning of the walk and may become larger as you proceed, but never become smaller along the way. When X is a single-digit number (empty step sequence) or a two-digit number (step sequence with only one element), there is no i for which the condition must hold, so it is always a smooth mountain path.

Examples:

  • The step sequence of X = 1234 is (|1-2|,\ |2-3|,\ |3-4|) = (1, 1, 1). Since 1 \leq 1 \leq 1, it is monotonically non-decreasing, so this is a smooth mountain path.
  • The step sequence of X = 3152 is (|3-1|,\ |1-5|,\ |5-2|) = (2, 4, 3). Since there is a position where 4 > 3, this is not a smooth mountain path.

You are given positive integers L and R. Find the number of integers between L and R (inclusive) that are smooth mountain paths, modulo 10^9 + 7.

Constraints

  • 1 \leq L \leq R < 10^{5000}
  • L and R are given in decimal notation without leading zeros. Therefore, the number of digits of L and the number of digits of R are each at most 5000.

Input

L
R
  • The first line contains the positive integer L representing the lower bound of the range, given in decimal notation.
  • The second line contains the positive integer R representing the upper bound of the range, given in decimal notation.

Output

Output in one line the number of smooth mountain paths between L and R (inclusive), modulo 10^9 + 7.

Sample Input 1

1
20

Sample Output 1

20

Sample Input 2

98
123

Sample Output 2

24

Sample Input 3

1000
50000

Sample Output 3

6624

Sample Input 4

123456789012345678901234567890
987654321098765432109876543210

Sample Output 4

426844825

Sample Input 5

1
1

Sample Output 5

1