@zero = [].size @one = :a.size @two = :aa.size @three = :aaa.size @seven = :aaaaaaa.size @nine = :aaaaaaaaa.size @ten = :aaaaaaaaaa.size @plus = :aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa.size.chr @mul = :aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa.size.chr @mod = eval(@ten.to_s + @mul + @mul + @nine.to_s + @plus + @seven.to_s) @div = :aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa.size.chr def matmul(a, b) c = [[@zero, @zero], [@zero, @zero]] a.size.times do |i| b.size.times do |j| b[@zero].size.times do |k| hoge = String.new() hoge << a[i][k].to_s hoge << @mul hoge << b[k][j].to_s hoge << @plus hoge << c[i][j].to_s c[i][j] = eval(hoge) hoge = String.new() hoge << c[i][j].to_s hoge << @div hoge << @mod.to_s c[i][j] = eval(hoge) end end end return c end def matpow(a, n) res = [[@one, @zero], [@zero, @one]] while n > @zero if (n & @one) > @zero res = matmul(res, a) end a = matmul(a, a) n >>= @one end return res end a = [[@zero, @one], [@one, @one]] t = gets.to_i t.times do n = gets.to_i b = matpow(a, n) hoge = String.new() hoge << b[@zero][@zero].to_s hoge << @plus hoge << b[@zero][@zero].to_s hoge << @plus hoge << b[@zero][@one].to_s ans = eval(hoge) hoge = ans.to_s hoge << @div hoge << @mod.to_s ans = eval(hoge) p ans end