Исправление задачи

Исправить программу так, чтобы она не зависала и при вводе

3

3 1

2 4 9

3 2

2 3 4

3 1000000000

1 2 3

Выход был:

13 22 35

29 47 76 

17711 999989061 6765

MOD = 1000000007

def add_mod(x, y):

  return (x + y) % MOD

def play_game(a1, a2, a3, k):

  for i in range(k):

    a1_new = add_mod(a2, a3)

    a2_new = add_mod(a1_new, a3)

    a3_new = add_mod(a1_new, a2_new)

    a1, a2, a3 = a1_new, a2_new, a3_new

  return a1, a2, a3

def main():

  t = int(input().strip())  

  for _ in range(t):

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

    a1, a2, a3 = map(int, input().strip().split())

    final_coords = play_game(a1, a2, a3, k)

    print(*final_coords)  

if name == "main":

  main()