<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:
        '''
        i want to do this dp from the first digit right ->

        do it by length of digits

        N = len(upper)

        for 1.... N - 1, do all

        then for length N, do contrained and unconstrained
        '''

    
        MOD = 10 ** 9 + 7
        
        def f(upper):

            @cache
            def free(index, prev):
                if index == 0:
                    return 1
                
                total = 0
                
                if prev != 9:
                    total += free(index - 1, prev + 1)

                if prev != 0:
                    total += free(index - 1, prev - 1)

                return total


            
            @cache
            def go(index, prev):
                if index == N:
                    return 1
             
                total = 0
        
                s = int(upper[index])

                if s > prev + 1:
                    if prev != 9:
                        total += free(N - (index + 1), prev + 1)
                    if prev != 0:
                        total += free(N - (index + 1), prev - 1)

                elif s == prev + 1:
                    if prev != 9:
                        total += go(index + 1, prev + 1)
                    if prev != 0:
                        total += free(N - (index + 1), prev - 1)


                elif s == prev:
                    if prev != 0:
                        total += free(N - (index + 1), prev - 1)
                        

                elif s == prev - 1:
                    if prev != 0:
                        total += go(index + 1, prev - 1)
                    
    
            

                return total
                

            best = 0
            char = int(upper[0])
            if char == 0:
                return 0

            N = len(upper)
            for L in range(1, N):
                for i in range(1, 10):
                    best += free(L - 1, i)
            
            
            for i in range(1, char):
                best += free(N - 1, i)
            
            best += go(1, char)

            return best


        return (f(high) - f(str(int(low) - 1))) % MOD
19800