#
# Home work #7
# Task 'Dyn6' (#1)
#

# принимаем на вход константы N и L, чёрный список клеток и список кэшированных результатов
def solve(_n: int, _l: int, _blacklisted: set, _cache: list) -> int:
    # вычислим количество возможных входов в каждую клетку из предыдущих,
    # основываясь на максимальной длине шага L (будем брать от 1 до L)

    # конкретно данная часть алгоритма проходит по всем клеткам, итерируя
    # шаги от неё на все возможные величины длин (от 1 до L), то есть
    # мы можем шагнуть дальше на кол-во клеток от 1 до L
    # если шаг возможен - увеличиваем счётчик входов для клетки, в которую шагнули

    # идём по всем клеткам до последней (от 1, нулевая нам не нужна, мы в неё не входим)
    for i in range(1, _n + 1):
        # если мы в клетке с лягушкой - не вычисляем в этом случае ничего
        if i in blacklisted:
            continue

        # для данной клетки делаем шаги длиной от 1 до L
        for j in range(i, i + _l):
            # спокойно можем перепрыгнуть за нужную клетку, учитываем это
            if j > _n:
                break

            # опять же можем прийти в клетку с лягушкой - нам это не надо
            if j in blacklisted:
                continue

            # пришли из данной клетки в какую-то доступную - увеличиваем счётчик входов для неё
            _cache[j] += 1

    # опять идём по всем клеткам и собираем кол-во входов в них
    for i in range(1, _n + 1):
        # хуесосим лягушек
        if i in blacklisted:
            continue

        # общее кол-во входов в данную клетку будет равно сумме
        # входов во все те клетки, из которых мы можем сюда придти
        # поэтому делаем отступ назад на кол-во шагов от 1 до L
        _sum = 0
        for j in range(i - _l, i):
            # опять можем выйти за допустимые границы или наступить на жабу, учитываем
            if j >= 0 and j not in blacklisted:
                # если все оке, то добавляем кол-во входов в клетку позади к общему кол-ву
                _sum += _cache[j]

        # записываем результат в кэш под нужным номером клетки
        _cache[i] = _sum

    # просто отладочные сообщения для наглядности, можно выпилить нахуй
    for i in range(1, _n + 1):
        if i not in blacklisted:
            print(f"Путей входа в точку #{i}:", _cache[i])

    # кол-во путей в последнюю клетку уже вычислено в кэше - просто достаём его оттуда
    return _cache[_n]


# из файла ввода нужны только первые две строки, вытащим их и закроем файл
input_file = open('ex1/input.txt', 'r', encoding='UTF-8')

first_line = input_file.readline().split(' ')
second_line = input_file.readline().split(' ')
input_file.close()

# из первой строки вытащим константы N и L (см. по заданию)
magic_number_n = int(first_line[0])
magic_number_l = int(first_line[1])

# числа во второй строке - это клетки с лягушками, занесём их в "чёрный список"
blacklisted = set(map(int, second_line))
# создадим список для кэшированных результатов предыдущих вычислений
# это и есть суть темы, правда с [0] у меня не работало, только вот с [1] всё норм
cache = [1] * (magic_number_n + 1)

# вызовем функцию решения задачи и выведем результат
result = solve(magic_number_n, magic_number_l, blacklisted, cache)
print('Result:', result)

# также результат нужно записать в файл по условию задания, тут всё понятно
output_file = open('ex1/output.txt', 'w', encoding='UTF-8')
content = list()
content.append(str(result))
output_file.writelines(content)
output_file.close()