Помогите решить задачу пайтон срочно

Посчитаем количество последовательностей, в которых есть 2 нуля подряд.
Первые два - нули:

 1 × 1 × kⁿ⁻² 

Без первого нуля, второй и третий - нули:

 (k - 1) × 1 × 1 × kⁿ⁻³ 

Без первого и второго нулей, третий и четвёртый - нули:

 (k - 1)² × 1 × 1 × kⁿ⁻⁴ 

И т.д.
Два последних - нули, остальные - не нули:

 (k - 1)ⁿ⁻² × 1 × 1 

Общее количество последовательностей с двумя нулями подряд - это сумма всех вышеперечисленных штук, т.к. каждая следующая комбинация исключает предыдущие.

 n-2

 Σ (k - 1)ᶨ  × kⁿ⁻²⁻ᶨ

j=0 

А общее количество последовательностей:

 kⁿ 

Из общего количества вычитаем количество последовательностей с двумя нулями.

Теперь, как вычислять сумму ряда. Можно раскрыть (k - 1) в степенях и считать по биному Ньютона, а можно тупо просуммировать степени, как есть. И в том, и в том случае получаем алгоритм линейно-логарифмической сложности от n, так что выбираем реализацию, которая проще (полагаемся на быструю питоновскую натуральную степень: https://github.com/python/cpython/blob/main/Objects/longobject.c ).

 n, k = map(int, map(input, ('',) * 2))

print(k ** n - sum((k - 1) ** j * k ** (n - 2 - j) for j in range(n - 1))) 

Примеры.
Ввод:

 2

2 

Вывод:

 3 

Ввод:

 3

9 

Вывод:

 712 

Ввод:

 4

7 

Вывод:

 2274 

А если нужно вводить два числа на одной строке, то так:

 n, k = map(int, input().split())

print(k ** n - sum((k - 1) ** j * k ** (n - 2 - j) for j in range(n - 1)))