<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:
        high=high[::-1]
        low=low[::-1]
        
        @cache
        def dp1(ld,k,f,
                # arr,
               ):
            
            if k>=len(high):
                
                if ld==0:return 0
                # if f==0:print(arr[::-1],f)
                return 1if f==0else 0
            
            # if ld!=0 and ld!=-1:
                # print(arr[::-1],f)
            a=1 if ld!=0 and ld!=-1 else 0
            l=max(ld-1,0) if ld!=-1 else 0
            u=min(ld+2,10) if ld!=-1 else 10
            for v in range(l,u):
                if v==ld:continue
                z=int(high[k])
                f1=1 if z<v else 0
                if z==v and f:f1=1
                a+=dp1(v,k+1,f1,
                      # arr+str(v)
                      )%1000000007
            return a
        @cache
        def dp2(ld,k,f,
                # arr,
               ):
            if k>=len(low):
                if ld==0:return 0
                # if f==0:print(arr[::-1],f,k)
                return 1if f==0else 0
            # print("K=",k,low))
            # if ld!=0 and ld!=-1:
            #     print(arr[::-1],f)
            a=1 if ld!=0 and ld!=-1 else 0
            l=max(ld-1,0) if ld!=-1 else 0
            u=min(ld+2,10) if ld!=-1 else 10
            for v in range(l,u):
                if v==ld:continue
                z=int(low[k])
                f1=1 if z<v else 0
                if z==v and f:f1=1
                a+=dp2(v,k+1,f1,
                      # arr+str(v)
                      )%1000000007
            return a
        
        r=(dp1(-1,0,0,
                     # ""
                    ) - dp2(-1,0,0,
                     # ""
                    ))%1000000007
        for x in range(1,len(low)):
            if abs(int(low[x-1])-int(low[x]))!=1:return r
        return (r+1)%1000000007
23000