<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:
        mod = 1000000007
        high = str(int(high)+1)

        @cache
        def dp1(n: int, k: int) -> int:            
            """
            Number of stepping numbers with k digits beginning with n
            """
            if k==1:
                return 1            
            if n==0:
                return dp1(1,k-1)
            if n==9:
                return dp1(8,k-1)            
            return (dp1(n-1,k-1) + dp1(n+1,k-1))%mod
        
        @cache
        def dp2(k: int) -> int:
            """
            Number of stepping numbers with k or less digits
            """
            if k==0:
                return 0       
            ans = 0
            for i in range(1,10):
                ans += dp1(i,k)
                ans %= mod
            return ans + dp2(k-1)
        
        def dfs(num: str, ind: int) -> int:
            ans = 0
            n = len(num)
            if ind == n:
                return 0
            if ind==0:                
                x = int(num[ind])
                for i in range(1,x):
                    ans += dp1(i,n-ind)
                    ans %= mod
                ans += dfs(num,ind+1)
                ans %= mod
            else:
                x = int(num[ind-1])
                y = int(num[ind])           
                for i in [x-1,x+1]:
                    if i>=0 and i<=9 and i<y:
                        ans += dp1(i,n-ind)
                        ans %= mod
                if abs(x-y)==1:
                    ans += dfs(num,ind+1)
                    ans %= mod
            return ans
        
        def steppingNumbersLT(num: str) -> int:
            """
            Number of stepping numbers in the range [0,num)
            """
            return dp2(len(num)-1) + dfs(num,0)
        
        return (steppingNumbersLT(high) - steppingNumbersLT(low))%mod
18800