Получение ошибки TLE в вызове тревоги Kickstart, Gooogle KickStart 2019

Question

Я пытаюсь решить проблему Kickstart Alarm , заданную в Учебном раунде KickStart 2019 . Это может быть найдено в https://codingcompetitions.withgoogle.com/kickstart/archive/2019

Делая математические преобразования, я получил общее выражение, которое вычисляет вклад каждого элемента по индексу "i" массива параметров "A" длины "N "до конечного результата.

[A[i] * (N - i)] * [K + (2^1 + 2^2 + ... + 2^K) + ... + ((i+1)^1 + (i+1)^2 + ... + (i+1)^K)], when i > 0
A[0] * N * K, otherwise

Я использовал модульную арифметику над модулем, заданным заданием, 10 ^ 9 + 7, пытаясь оптимизировать вычисления. Ниже приведено решение, реализованное в Python 3.5, которое я попробовал.

def generate_parameter_array(N, x, y, C, D, E1, E2, F):
    array = [(x + y) % F]
    for i in range(N - 1):
        old_x = x
        x = (C * x + D * y + E1) % F
        y = (D * old_x + C * y + E2) % F
        array.append((x + y) % F)
    return array

def solution():
    T = int(input())
    mypow = pow
    for t in range(1, T + 1):
        test_case = [int(n) for n in input().split(" ")]
        N = test_case[0] # Length of the parameter array
        K = test_case[1] # Number of exponential powers
        A = generate_parameter_array(N, *(test_case[2:]))
        result = 0
        mod = 10**9 + 7
        P_sum = K # accumulator of the geometric progressions
        for i in range(1, N):
            P_sum = (P_sum + ((mypow(i+1, K+1, mod) - (i+1)) * (mypow(i,mod-2,mod)))) % mod
            result = (result + (((A[i] * (N - i)) % mod) * P_sum) % mod) % mod
        result = (result + (((A[0] * N) % mod) * K) % mod) % mod
        print('Case #{}: {}'.format(t, result))

Это решение превышает лимит времени, установленный для скрытого набора тестов, я получаю ошибку TLE. Есть ли способ более оптимизировать этот алгоритм, или я ограничен Python? Пожалуйста, укажите на мои ошибки. Спасибо!