458

p458.py

from numpy import *

# The Matrix!
x = matrix([
[1,6,0,0,0,0],
[1,1,5,0,0,0],
[1,1,1,4,0,0],
[1,1,1,1,3,0],
[1,1,1,1,1,2],
[1,1,1,1,1,1],
])

# use something higher than 10**9, for safety
prec = 10**20

f = matrix([1,1,1,1,1,1])
f = transpose(f)


n = 10**12-1
# trick is to break down the matrix power by powers of 2
b = str(bin(n)[2:-1])[::-1]

# silly hack: see if the number is even or odd
tot = x * (n % 2)
for i in b:
  x = x**2 % prec
  if i == "1":
    tot = (x * tot) % prec

print (tot * f * 7)[0] % 10**9