задача на количество пилообразных последовательностей

Представим, что для некой длины M мы имеем:

• массив UP длиной k+1, ячейка UP[k] которого содержит количество пилообразных последовательностей длиной M, заканчивающихся числом k, а перед этим было меньшее число (отсюда название. Понятно, что UP[1] = 0)
• а также массив DOWN той же длины, ячейка DOWN[k] которого содержат количество пилообразных последовательностей длиной M, заканчивающихся числом k, а перед этим было большее число (ясно, что DOWN[k] = 0)

Например, для M=3, k=3 UP[2] = 2 - это [2,1,2] и [3,1,2], но сами последовательности мы не генерируем

Заполняем массивы шаг за шагом (понадобится четыре массива - для текущего и для следующего шага). Значение в ячейке нового массива UP - это сумма некой части старого массива DOWN и наоборот. В конце, после N-го шага, суммируем все ячейки обоих массивов.

Для 100,100 считается доли секунды, ответ 3773018431531573052522230433297637206758217297263096271159156235247115149777810286853214926143448593916049821132944802103999840915098829452130589430766903146390723369894978956835816, так что для ограничения результата 32-битным числом проблем со временем не будет.

Стоит посмотреть, не подчиняются ли значения какой-то закономерности. Вдруг формула простая получится...

n, k = map(int, input().split())
down, up = list(range(k - 1, -1, -1)), list(range(k))
for i in range(3, n + 1):
  down, up = ([sum(up[j + 1:]) for j in range(k)],
              [sum(down[:j]) for j in range(k)])
print(sum(up) + sum(down))