from typing import List
import itertools


def check_increasing(number: str):
    prev_num: int = -1
    if len(number) > 1 and int(number[0]) == 0:
        return False

    for num in number:
        if int(num) >= prev_num:
            prev_num = int(num)
        else:
            return False
    return True


def lower_than_res(res: str, numbers: str):
    for (i, x) in enumerate(numbers):
        if x >= res[0]:
            return i

    return 0

def count_numbers(length: int, numbers: str):
    result: List[str] = [x for x in numbers]
    while length-1> 0:
        for i, res in enumerate(result.copy()):
            # Remove previous step
            result.remove(res)

            # Don't calculate unnecessary things
            i_lower = lower_than_res(res, numbers) 
            for num in numbers[i_lower:]:
                if i != 0 and res[-1] == "0":
                    continue
                if num >= res[-1] and res[-1] != "0":
                    result.append(res + num)

        length -= 1

    print(len(result))
    return len(result)


# Way too slow on the last test
def count_numbers2(length: int, numbers: str):
    result: int = 0
    for comb in itertools.product(numbers, repeat=length):
        # print(comb, check_increasing(comb))
        if check_increasing(comb):
            result += 1

    print(result)
    # print()
    return result


if __name__ == "__main__":
    assert count_numbers(5, "1") == 1
    assert count_numbers(1, "0") == 1
    assert count_numbers(3, "123") == 10
    assert count_numbers(2, "0") == 0
    assert count_numbers(2, "137") == 6
    assert count_numbers(8, "25689") == 495
    assert count_numbers(10, "12") == 11
    assert count_numbers(10, "123456789") == 43758