<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>

N = 101
D = [[0]*N for _ in range(10)]
S = [0] * N
MOD = 1000000007
class Solution:
    def countSteppingNumbers(self, low: str, high: str) -> int:
        if D[1][1] == 0:
            for i in range(1, 10):
                D[i][1] = 1
            for l in range(2, N):
                for i in range(2, 9):
                    D[i][l] = (D[i-1][l-1] + D[i+1][l-1]) % MOD
                D[9][l] = D[8][l-1]
                D[1][l] = (D[2][l-1] + (D[1][l-2] if l > 2 else 1)) % MOD
            S[0] = 1
            S[1] = 9
            for l in range(2, N):
                for i in range(1, 10):
                    S[l] = (S[l] + D[i][l]) % MOD
            for i in range(2, N):
                S[i] += S[i-1]
        #print('s2=', S[2])
        def upto(high):
            if len(high) == 1:
                return int(high)
            n = len(high)
            res = S[n-1]
            for i in range(1, int(high[0])):
                res = (res + D[i][n]) % MOD
                
            #print('resss = ', res)
            j = 1
            while j < n:
                hj = int(high[j])
                lj = int(high[j-1])
                if hj > lj + 1:
                    res = (res + D[lj+1][n - j]) % MOD
                    if lj > 1:
                        res = (res + D[lj-1][n - j]) % MOD
                    elif lj == 1:
                        res = (res + (1 if n - j - 1 <= 0 else D[1][n-j-1])) % MOD
                    break
                elif hj == lj + 1:
                    if lj > 1:
                        res = (res + D[lj-1][n - j]) % MOD
                        j += 1
                    elif lj == 1:
                        res = (res + (1 if n - j - 1 <= 0 else D[1][n-j-1])) % MOD
                        j += 1
                    else:
                        j += 1
                elif hj == lj:
                    if lj > 1:
                        res = (res + D[lj-1][n - j]) % MOD
                    elif lj == 1:
                        res = (res + (1 if n-1-j <= 0 else D[1][n-1-j])) % MOD
                    else:
                        #res = (res + D[1][n-j]) % MOD
                        break
                    break
                elif hj == lj - 1:
                    j += 1
                else:
                    break
                #print('j=', j, 'res = ', res)
            if j == n:
                res = (res + 1) % MOD
            return res
        
        #print('u(%d) = %d, %d' % (int(high), upto(high), upto(str(int(low)-1))))
        if low == '1':
            return upto(high)
        return (upto(high) - upto(str(int(low) - 1))) % MOD
                
16800