<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:
        
        def ddp(num):
            if num < 10:
                return num
            
            s = str(num)
            lens = len(s)
            s0 = int(s[0])
            # isnum, islim, lastn
            dp = defaultdict(int)

            dp[(0, 0, 0)] = 1
            dp[(1, 1, s0)] = 1
            for i in range(1, s0):
                dp[(1, 0, i)] = 1


            for i in range(1, lens):
                s0 = int(s[i])
                tmp = defaultdict(int)
                for (isnum, islim, lastn), val in dp.items():

                    if isnum == 0:
                        for i in range(1, 10):
                            tmp[(1, 0, i)] += val
                        tmp[(0, 0, 0)] = 1

                    else:
                        if islim == 1:
                            if lastn - 1 == s0:
                                tmp[(1, 1, lastn - 1)] += val
                            elif 0 <= lastn - 1 < s0:
                                tmp[(1, 0, lastn - 1)] += val
                            if lastn + 1 == s0:
                                tmp[(1, 1, lastn + 1)] += val
                            elif lastn + 1 < s0:
                                tmp[(1, 0, lastn + 1)] += val

                        else:
                            if lastn - 1 >= 0:
                                tmp[(1, 0, lastn - 1)] += val
                            if lastn + 1 < 10:
                                tmp[(1, 0, lastn + 1)] += val

                dp = tmp

            res = 0
            for (isnum, islim, lastn), val in dp.items():
                if isnum == 1:
                    res += val

            return res
            

        mod = 10**9 + 7

        return (ddp(int(high)) - ddp(int(low) - 1)) % mod

16700