<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:
    def countSteppingNumbers(self, low: str, high: str) -> int:
        low = [int(c) for c in low]
        high = [int(c) for c in high]
        nl, nh = len(low), len(high)
        MOD = 1_000_000_007
        
        @cache
        def dp(i, prev, lt, typ):
            if typ == 'L':
                n = nl
                arr = low
            else:
                n = nh
                arr = high
            if i == n:
                return 1
            res = 0
            if prev == -1:
                for v in range(10):
                    res = (res + dp(i + 1, v if v else -1, True, typ)) % MOD
            else:
                for v in prev + 1, prev - 1:
                    if 0 <= v < 10:
                        if not lt and v > arr[i]:
                            continue
                        res = (res + dp(i + 1, v, lt or v < arr[i], typ)) % MOD
            return res
        
        xl = 0
        for v in range(low[0] + 1):
            xl = (xl + dp(1, v if v else -1, v < low[0], 'L')) % MOD
                
        xh = 0
        for v in range(high[0] + 1):
            xh = (xh + dp(1, v if v else -1, v < high[0], 'H')) % MOD
        
        extra = 0
        if len(low) == 1 or all(abs(low[i] - low[i + 1]) == 1 for i in range(nl - 1)):
            extra = 1
        return (xh - xl + extra) % MOD
        
24300