require <<__EOF__.chomp matrix __EOF__ class Matrix alias_method :mul, ?).succ.intern end zc = (?J...?z).to_a.size.chr onec = (?I...?z).to_a.size.chr sevenc = (?C...?z).to_a.size.chr M = [onec, zc, zc, zc, zc, zc, zc, zc, zc, sevenc].join.to_i O = [].size I = [p].size mat = Matrix[[I, I], [I, O]] def f(a, n) if n == I a elsif n.even? f (a.mul a).map{|x|x.modulo M}, n>>I else (f((a.mul a).map{|x|x.modulo M}, n>>I).mul a).map{|x|x.modulo M} end end T = gets.to_i readlines.map{|s| n = s.to_i if n == I p I else a = f(mat, n.pred)[I, O] b = f(mat, n.succ)[I, O] p a.send(?).succ.succ, b).modulo M end }