<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>

MOD = 10**9 + 7

class Solution:
    def __init__(self):
        self.dp = {}

    def helper(self, pos, tight, isZero, prevDigit, s):
        if pos == len(s):
            return 0 if isZero else 1

        if (pos, tight, isZero, prevDigit) in self.dp:
            return self.dp[(pos, tight, isZero, prevDigit)]

        res = 0
        limit = int(s[pos]) if tight else 9

        for curDigit in range(0, limit + 1):
            newTight = tight and (curDigit == limit)
            willBeZero = isZero and (curDigit == 0)

            if isZero:
                res += self.helper(pos + 1, newTight, willBeZero, curDigit, s)
            else:
                if abs(curDigit - prevDigit) == 1:
                    res += self.helper(pos + 1, newTight, willBeZero, curDigit, s)

            res %= MOD

        self.dp[(pos, tight, isZero, prevDigit)] = res
        return res

    def countSteppingNumbers(self, low, high):
        self.dp = {}
        l = self.helper(0, True, True, -1, low)

        self.dp = {}
        r = self.helper(0, True, True, -1, high)

        res = (r - l) % MOD
        res = (res + MOD) % MOD

        add = True
        for i in range(1, len(low)):
            if abs(int(low[i]) - int(low[i - 1])) != 1:
                add = False
                break
        if add:
            res = (res + 1) % MOD

        return res

16900