2777.poti

tipo Mat = Lista[Lista[BigInt]]
m = 1000000007

matrixMult(a, b: Mat): Mat
  var result := Lista(a.tamanho, Lista(a[1].tamanho, BigInt(0)))
  para i de 1 até a.tamanho, j de 1 até b.tamanho, k de 1 até b.tamanho faça
    result[i][j] := (result[i][j] + a[i][k] * b[k][j]) mod m
  fim
  retorne result
fim

matrixPow(a: Mat, n: BigInt): Mat =
  se n == 1 então
    a
  senão
    b = matrixPow(a, n div 2)
    c = matrixMult(b, b)
    se n mod 2 == 0 então c senão matrixMult(a, c) fim
  fim

dabriel(n: BigInt): BigInt
  x0: Mat = [[1, 2, 2]]
  a: Mat = [[0, 1, 0], [0, 0, 1], [1, 1, 0]]
  xn: Mat = matrixMult(x0, matrixPow(a, n - 1))
  retorne xn[1][1]
fim

var n := leia_texto
enquanto não eof faça
  se n == "0" então
    escreva 1
  senão
    escreva dabriel(BigInt(n))
  fim
  n := leia_texto
fim