<p>Given two positive integers <code>low</code> and <code>high</code> represented as strings, find the count of <strong>stepping numbers</strong> in the inclusive range <code>[low, high]</code>.</p>

<p>A <strong>stepping number</strong> is an integer such that all of its adjacent digits have an absolute difference of <strong>exactly</strong> <code>1</code>.</p>

<p>Return <em>an integer denoting the count of stepping numbers in the inclusive range</em> <code>[low, high]</code><em>. </em></p>

<p>Since the answer may be very large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p><strong>Note:</strong> A stepping number should not have a leading zero.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> low = &quot;1&quot;, high = &quot;11&quot;
<strong>Output:</strong> 10
<strong>Explanation: </strong>The stepping numbers in the range [1,11] are 1, 2, 3, 4, 5, 6, 7, 8, 9 and 10. There are a total of 10 stepping numbers in the range. Hence, the output is 10.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> low = &quot;90&quot;, high = &quot;101&quot;
<strong>Output:</strong> 2
<strong>Explanation: </strong>The stepping numbers in the range [90,101] are 98 and 101. There are a total of 2 stepping numbers in the range. Hence, the output is 2. </pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= int(low) &lt;= int(high) &lt; 10<sup>100</sup></code></li>
	<li><code>1 &lt;= low.length, high.length &lt;= 100</code></li>
	<li><code>low</code> and <code>high</code> consist of only digits.</li>
	<li><code>low</code> and <code>high</code> don&#39;t have any leading zeros.</li>
</ul>

class Solution:
    '''
    iterate i from 1 to |len| - 1
    M[i][j]: #stepping numbers of i digits ending with j
    M[i][j] = M[i-1][j-1] + M[i-1][j+1], for j in {1,2,...,8}
    M[i][0] = M[i-1][1]
    M[i][9] = M[i-1][8]

    M[0][j] = 1 for j in {1-9}

    when iterate to |len|:
      M[i][j][k]: #stepping numbers of i digits ending with j, k(0/1) if reaching limit
      M[i][j][0] = (M[i-1][j-1][0] + M[i-1][j+1][0])
                 + (M[i-1][j-1][1] if j < s[i]) + (M[i-1][j-1][1] if j < s[i])
      M[i][j][1] = M[i-1][j-1][1] if s[i] is 'j'
      M[0][k][0] = 1 if 'k' < s[0]
      M[0][k][1] = 1 if 'k' == s[0]
    '''
    def count(self, limit: str) -> int:
      mod = 1000000007
      res = 0
      limit_len = len(limit)
      if limit_len == 1:
        return int(limit)
      M = [[0] * 10 for _ in range(limit_len - 1)]
      adjacent_digit = {0: [1], 9: [8]}
      for n in range(1, 9):
        adjacent_digit[n] = [n - 1, n + 1]
      for j in range(1, 10):
        M[0][j] = 1
        res += 1
      for i in range(1, limit_len - 1):
        for j in range(10):
          for prev in adjacent_digit[j]:
            M[i][j] += M[i-1][prev]
            M[i][j] %= mod
            res = (res + M[i-1][prev]) % mod
      X = [[[0] * 2 for _ in range(10)] for _ in range(limit_len)]
      first_digit = int(limit[0])
      for j in range(1, first_digit):
        X[0][j][0] = 1
      X[0][first_digit][1] = 1
      for i in range(1, limit_len):
        for j in range(10):
          for prev in adjacent_digit[j]:
            X[i][j][0] += X[i-1][prev][0]
            X[i][j][0] %= mod
            # print('a', i, j)
            # res = (res + X[i-1][prev][0]) % mod
            if j < ord(limit[i]) - ord('0'):
              X[i][j][0] += X[i-1][prev][1]
              X[i][j][0] %= mod
              # res = (res + X[i-1][prev][1]) % mod
            elif j == ord(limit[i]) - ord('0'):
              # if i == 2 and j == 1: print('b', i, j, prev)
              X[i][j][1] += X[i-1][prev][1]
              X[i][j][1] %= mod

      for [x, y] in X[limit_len-1]:
        # print(x, y)
        res = (res + x + y) % mod
      # print(X, len(X), len(X[0]))
      return res

    def countSteppingNumbers(self, low: str, high: str) -> int:
        large = self.count(high)

        small = self.count(str(int(low) - 1))
        print('small', small, 'large', large)
        mod = 1000000007
        return (large - small + mod) % mod

17100