<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, high):
        # Constants and initial setup
        mod = 1_000_000_007
        n = len(high)
        
        # Pad the 'low' string with leading zeros to match the length of 'high'
        low = low.rjust(n, '0')
        
        # Use memoization to cache results of the recursive function
        from functools import lru_cache
        
        @lru_cache(None)
        def dfs(idx, prev, aboveLow, belowHigh, init0):
            # Base case: if we've processed all digits, return 1
            if idx == n:
                return 1
            
            # Initialize result for this state
            res = 0
            
            # Determine the range of the next digit
            l = int(low[idx])
            h = int(high[idx])
            
            # Iterate over possible next digits
            for next_digit in range(0 if aboveLow else l, 10 if belowHigh else h + 1):
                # Check if the next digit is valid (either initial zero or stepping condition met)
                if not init0 or abs(prev - next_digit) == 1:
                    # Recursive call to process the next digit
                    res += dfs(
                        idx + 1,  # Move to the next digit
                        next_digit,  # Current digit becomes the previous digit for the next call
                        aboveLow or next_digit > l,  # Check if we are above the lower bound
                        belowHigh or next_digit < h,  # Check if we are below the upper bound
                        init0 or next_digit != 0  # Check if we have an initial zero
                    )
            
            # Return the result modulo 10^9 + 7
            return res % mod
        
        # Start the recursive DFS from the first digit
        return dfs(0, -1, False, False, False)
18700