<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:
        # result = 0
        # for i in range(int(low), int(high)+1):
        #     if is_stepping_number(str(i)):
        #         result += 1
        #         result %= 1e9 + 7
        # return int(result)
        # Example usage
        start = int(low)
        end = int(high)
        # stepping_numbers = generate_stepping_numbers(start, end)
        # print(f"Stepping numbers between {start} and {end}: {stepping_numbers}")
        # return int(len(stepping_numbers) % (1e9 + 7))
        # return int(count_stepping_numbers_old(start, end))
        return count(low, high)

def count_stepping_numbers(start, end, chunk_size=1_000_000):
    def dfs(num, current_start, current_end):
        if current_start <= num <= current_end:
            count[0] += 1
        if num > current_end:
            return
        last_digit = num % 10
        if num == 0:
            for i in range(1, 10):
                dfs(i, current_start, current_end)
        else:
            if last_digit > 0:
                dfs(num * 10 + (last_digit - 1), current_start, current_end)
            if last_digit < 9:
                dfs(num * 10 + (last_digit + 1), current_start, current_end)

    cache = {}
    total_count = 0
    start_chunk = math.floor(start / chunk_size)
    end_chunk = math.ceil(end / chunk_size)

    # Count for full chunks
    for chunk in range(start_chunk, end_chunk + 1):
        chunk_start = max(start, chunk * chunk_size)
        chunk_end = min(end, (chunk + 1) * chunk_size - 1)
        
        if (chunk_start, chunk_end) in cache:
            total_count += cache[(chunk_start, chunk_end)]
        else:
            count = [0]
            dfs(0, chunk_start, chunk_end)
            cache[(chunk_start, chunk_end)] = count[0]
            total_count += count[0]

    return total_count

def count_stepping_numbers_oldld(start, end):
    def initialize_dp():
        dp = [[0] * 10 for _ in range(11)]
        prefix_sum = [[0] * 10 for _ in range(11)]
        total_sum = [0] * 11

        # Base case: 1-digit numbers
        for i in range(10):
            dp[1][i] = 1
        
        # Fill dp table
        for digit_len in range(2, 11):
            for last_digit in range(10):
                if last_digit > 0:
                    dp[digit_len][last_digit] += dp[digit_len-1][last_digit-1]
                if last_digit < 9:
                    dp[digit_len][last_digit] += dp[digit_len-1][last_digit+1]

        # Calculate prefix sums and total sums
        for digit_len in range(1, 11):
            curr_sum = 0
            for last_digit in range(10):
                curr_sum += dp[digit_len][last_digit]
                prefix_sum[digit_len][last_digit] = curr_sum
            total_sum[digit_len] = curr_sum

        return dp, prefix_sum, total_sum

    def count_up_to(n):
        if n < 10:
            return n

        str_n = str(n)
        digit_len = len(str_n)
        result = sum(total_sum[1:digit_len])  # All numbers with less digits

        for i in range(digit_len):
            curr_digit = int(str_n[i])
            
            if i == 0:
                result += prefix_sum[digit_len][curr_digit - 1]
            else:
                prev_digit = int(str_n[i-1])
                if curr_digit < prev_digit:
                    result += prefix_sum[digit_len-i][curr_digit]
                elif curr_digit > prev_digit:
                    result += prefix_sum[digit_len-i][curr_digit - 1]
                else:
                    return result  # Not a stepping number

            if i == digit_len - 1 and abs(int(str_n[i]) - int(str_n[i-1])) == 1:
                result += 1  # Count the number itself if it's a stepping number

        return result

    dp, prefix_sum, total_sum = initialize_dp()
    return count_up_to(end) - count_up_to(start - 1)

def count_stepping_numbers_old(start, end):
    @lru_cache(maxsize=32)
    def dfs(num, start, end):
        if start <= num <= end:
            count[0] += 1
            if count[0] == (1e9 + 7):
                count[0] = 0
         
        if num > end:
            return
        
        last_digit = num % 10
        
        if num == 0:
            for i in range(1, 10):
                dfs(i, start, end)
        else:
            if last_digit > 0:
                dfs(num * 10 + (last_digit - 1), start, end)
            if last_digit < 9:
                dfs(num * 10 + (last_digit + 1), start, end)

    count = [0]  # Using a list to allow modification in nested function
    dfs(0, start, end)
    return count[0]

def count(low, high):
    mod=10**9+7
    def solve(high):
        @cache 
        def dp(idx,tight,last,nz):
            if idx==len(high): return 1
            ans=0
            h=10 if not tight else int(high[idx])+1
            for i in range(h):
                if not nz or abs(i-last)==1: ans+=dp(idx+1,1 if (tight and i==int(high[idx])) else 0,i,nz | (i!=0))
                ans%=mod
            return ans
        return dp(0,1,0,0)
    return (solve(high)-solve(str(int(low)-1)))%mod        

from itertools import pairwise

# def diff(l):
#     # print([abs(y-x) for (x, y) in pairwise(l)])
#     return [abs(y-x) for (x, y) in pairwise(l)]

def all_ones(l):
    for (x, y) in pairwise(l):
        if abs(int(x)-int(y)) != 1:
            return False
    return True

def is_stepping_number(x: str):
    l = list(x)
    if len(l) == 1:
        return True
    # l = [x) for x in l]
    return all_ones(l)

def generate_stepping_numbers(start, end):
    def is_stepping_number(num):
        num_str = str(num)
        for i in range(1, len(num_str)):
            if abs(int(num_str[i]) - int(num_str[i-1])) != 1:
                return False
        return True

    def dfs(num, start, end, result):
        if start <= num <= end:
            result.append(num)
        
        if num > end:
            return
        
        last_digit = num % 10
        
        if num == 0:
            for i in range(1, 10):
                dfs(i, start, end, result)
        else:
            if last_digit > 0:
                dfs(num * 10 + (last_digit - 1), start, end, result)
            if last_digit < 9:
                dfs(num * 10 + (last_digit + 1), start, end, result)

    result = []
    dfs(0, start, end, result)
    return sorted(result)



20900