class TriBonacci
  def initialize
    @mg = {0=>3, 1=>1, 2=>3}
    @mh = {0=>1, 1=>3, 2=>-1}
  end

  def f(n)
    (5*g(n) + g(n+1) + 2*g(n+2)) / 22
  end

  def g(n)
    return @mg[n] if @mg[n]
    return @mg[n] = @mg[n-3] + @mg[n-2] + @mg[n-1] if @mg[n-1] && @mg[n-2] && @mg[n-3]
    m = n / 2
    @mg[n] = n % 2 == 0 ? g(m)**2 - 2*h(m+1) : g(m)*g(m+1) + h(m) - h(m+1)
  end

  def h(n)
    return @mh[n] if @mh[n]
    return @mh[n] = @mh[n-3] - @mh[n-2] - @mh[n-1] if @mh[n-1] && @mh[n-2] && @mh[n-3]
    m = n / 2
    @mh[n] = n % 2 == 0 ? h(m)*h(m+1) - g(m) + g(m+1) : h(m+1)**2 - 2*g(m)
  end
end

n = 6500
p TriBonacci.new.f(n)