Размер таблицы невелик, а не проходит по памяти, видимо, потому, что вы заполняете таблицу длинными числами, и берёте остаток по модулю только в конце.

Выполняйте % 1000000007 при каждом сложении

Пилообразные последовательности бывают зубьями вверх и зубьями вниз. Их одинаковое количество. Код из вопроса считает их по отдельности, можно ускориться в два раза. n = 1 становится отдельным случаем.

def n_seqs(n, k):
    if n == 1:
        return k
    mod = 10 ** 9 + 7 
    a = [1] * (k - 1)
    for _ in range(1, n):
        b = []
        s = 0
        for ai in a:
            s = (s + ai) % mod
            b.append(s)
        a = b[::-1]
    return 2 * sum(a) % mod


print(n_seqs(*map(int, input().split())))

Памяти нужно мало. А время – почти секунда на максимальных размерах:

$ time -p echo 4000 4000 | python sawlike.py
380392195
real 0.62
user 0.62
sys 0.00

Код выше считает последовательности у которых один конец свободен, второй фиксирован: последовательность заканчивается определённым значением. Разобьём n примерно пополам, сосчитаем количество "половинок" последовательностей, умножим левые половинки на правые. Это улучшит время в два раза.

MOD = 10 ** 9 + 7 


def step(a):
    b = []
    s = 0
    for ai in a:
        s = (s + ai) % MOD
        b.append(s)
    return b[::-1]


def n_seqs(n, k):
    if n == 1:
        return k

    a = [1] * (k - 1)
    for _ in range((n - 1) // 2):
        a = step(a)
    l = a
    r = step(a) if n % 2 == 0 else a
    return 2 * sum(li * ri for li, ri in zip(l, r)) % MOD


print(n_seqs(*map(int, input().split())))

$ time -p echo 4000 4000 | python sawlike.py
380392195
real 0.33
user 0.32
sys 0.00

К сожалению, подход не масшабируется: если думать о дальнейшем разбиении пополам и разделяй-и-властвуй, нам понадобятся последовательности с фиксированными обоими концами, а их k². Это тоже самое что перевести задачу на язык матриц: step описывает линейное отображение, которое представляется матрицей. Задача решается быстрым возведение этой матрицы в степень n - 1. Размер матрицы k². Время будет хуже чем k²log n, память такая же. А у нас уже есть алгоритм nk c памятью k. Такая оптимизация наоборот, она хорошо работает если k < √n. Остаётся надежда что матричное представление избыточно и можно организовать вычисления на структурах линейных по k. Я таких структур не придумал.

Динамика по k не сложилась.

Можно раскопать производящие функции:

• k = 3 даёт последовательность 3, 6, 10, 16, 26, .... Начиная со второго элемента это удвоенные числа Фибоначчи.

• k = 4 даёт последовательность 4, 12, 28, 62, 140, .... Начиная со второго элемента это удвоенные элементы A077998.

Я попробовал исправить код автора. Не знаю, пройдёт ли по ограничениям.

import os

def calculate_zigzag_patterns(length, max_value):
    MOD = 10**9 + 7

    if length == 1:
        return max_value

    increasing = [0] * (max_value + 1)
    decreasing = [0] * (max_value + 1)

    for index in range(1, max_value + 1):
        increasing[index] = 1
        decreasing[index] = 1

    for current_length in range(2, length + 1):
        new_increasing = [0] * (max_value + 1)
        new_decreasing = [0] * (max_value + 1)

        total_decreasing = 0
        for last_value in range(1, max_value + 1):
            total_decreasing = (total_decreasing + decreasing[last_value - 1]) % MOD
            new_increasing[last_value] = total_decreasing

        total_increasing = 0
        for last_value in range(max_value, 0, -1):
            if last_value < max_value:
                total_increasing = (total_increasing + increasing[last_value + 1]) % MOD
            new_decreasing[last_value] = total_increasing

        increasing, new_increasing = new_increasing, increasing
        decreasing, new_decreasing = new_decreasing, decreasing

    final_result = sum(increasing[last_value] + decreasing[last_value] for last_value in range(1, max_value + 1)) % MOD
    return final_result

length, max_value = 20, 3
result = calculate_zigzag_patterns(length, max_value)
print(result)

os.system("pause")