require 'matrix' a,b,n=gets.split.map(&:to_i) $mod = 1000000007 $memo={} def rui(m,x) m.map!{|e|e%$mod} return $memo[x] if($memo.key?(x)) # p m if x==1 m else return $memo[x] = if x.even? rui(m,x/2)*rui(m,x/2).map!{|e|e%$mod} else rui(m,x-1)*m.map!{|e|e%$mod} end end end ma = Matrix[[a, b], [1, 0]] p (rui(ma,n)*Matrix[[1],[0]])[1,0]%$mod.ceil