def matNula(f, c):
m = []
for i in range(f):
m.append([0]*c)
return m
def expmat(m, e):
if e==1:return m
r= expmat(m,e//2)
r =mulMat(r,r)
if e % 2:r=mulMat(r, m)
return r
def mulMat(m1,m2):
acum = matNula(len(m1),len(m2[0]))
for i in range(len(m1)):
for j in range(len(m2[0])):
for k in range(len(m2)):
acum[i][j]+= m1[i][k]*m2[k][j]
return acum
def trif(n):
if n==1:return 1
if n==2:return 1
if n==3:return 1
coeficientes = [[1,1,1],[1,0,0],[0,1,0]]
casos_base = [[1],[1],[1]]
return mulMat(expmat(coeficientes,n-3), casos_base)[0][0]
print(trif(4)) # Output: 5
ZGVmIG1hdE51bGEoZiwgYyk6CiAgICBtID0gW10KICAgIGZvciBpIGluIHJhbmdlKGYpOgogICAgICAgIG0uYXBwZW5kKFswXSpjKQogICAgcmV0dXJuIG0KCmRlZiBleHBtYXQobSwgZSk6CiAgICBpZiBlPT0xOnJldHVybiBtCiAgICByPSBleHBtYXQobSxlLy8yKQogICAgciA9bXVsTWF0KHIscikKICAgIGlmIGUgJSAyOnI9bXVsTWF0KHIsIG0pCiAgICByZXR1cm4gcgoKZGVmIG11bE1hdChtMSxtMik6CiAgICBhY3VtID0gbWF0TnVsYShsZW4obTEpLGxlbihtMlswXSkpCiAgICBmb3IgaSBpbiByYW5nZShsZW4obTEpKToKICAgICAgICBmb3IgaiBpbiByYW5nZShsZW4obTJbMF0pKToKICAgICAgICAgICAgZm9yIGsgaW4gcmFuZ2UobGVuKG0yKSk6CiAgICAgICAgICAgICAgICBhY3VtW2ldW2pdKz0gbTFbaV1ba10qbTJba11bal0KICAgIHJldHVybiBhY3VtCgpkZWYgdHJpZihuKToKICAgIGlmIG49PTE6cmV0dXJuIDEKICAgIGlmIG49PTI6cmV0dXJuIDEKICAgIGlmIG49PTM6cmV0dXJuIDEKICAgIGNvZWZpY2llbnRlcyA9IFtbMSwxLDFdLFsxLDAsMF0sWzAsMSwwXV0KICAgIGNhc29zX2Jhc2UgPSBbWzFdLFsxXSxbMV1dCiAgICByZXR1cm4gbXVsTWF0KGV4cG1hdChjb2VmaWNpZW50ZXMsbi0zKSwgY2Fzb3NfYmFzZSlbMF1bMF0KCnByaW50KHRyaWYoNCkpICAjIE91dHB1dDogNQo=