#!ruby -nrmatrix
m=Matrix[*(0..35).map{|i|3759473158[i]}.each_slice(6)]**~-$_.to_i*Matrix[[1],[0],[0],[1],[0],[1]]
p (m[0,0]+m[1,0]+m[2,0]).%10**9+7