百度笔试-咋过不了

第二题
--------------------
# 矩阵快速幂，咋也过不了
line = input().split(' ')
line = list(map(int, line))
a1, a2, a3, a4 = line[0], line[1], line[2], line[3]
n = line[4]
mod = int(pow(10, 9)+7)
base = [[0, 1, 0, 0],
        [0, 0, 1, 0],
        [0, 0, 0, 1],
        [1, 1, 0, 1]]

init = [[a1],
        [a2],
        [a3],
        [a4]]


def matmul(m1, m2):
  x, y, z = len(m1), len(m1[0]), len(m2[0])
  m3 = [[0 for _ in range(z)] for _ in range(x)]
  for i in range(x):
    for j in range(z):
      for k in range(y):
        m3[i][j] += m1[i][k] * m2[k][j]
        m3[i][j] %= mod
  return m3


if n <= 4:
  print(line[n-1])
else:
  result = [[1, 0, 0, 0],
            [0, 1, 0, 0],
            [0, 0, 1, 0],
            [0, 0, 0, 1]]
  n = n-4
  while n > 0:
    if n & 0x1:
      result = matmul(result, base)
    base = matmul(base, base)
    n >>= 1
  print(matmul(result, init)[3][0]%mod)