N = gets.to_i
C, D = (1..N).map {gets.split.map(&:to_i)}.transpose
M = 10**9 + 7
ans = C.zip(D).map {|c, d|
  x = if c == 1
        2
      elsif c == 2
        3
      else
        t = c - 2
        z = [[1, 1], [1, 0]]
        y = [[1, 0], [0, 1]]
        while t > 0
          if t % 2 == 1
            y = [[(y[0][0] * z[0][0] + y[0][1] * z[1][0]) % M, (y[0][0] * z[0][1] + y[0][1] * z[1][1]) % M],
                 [(y[1][0] * z[0][0] + y[1][1] * z[1][0]) % M, (y[1][0] * z[0][1] + y[1][1] * z[1][1]) % M]]
          end
          z = [[(z[0][0] * z[0][0] + z[0][1] * z[1][0]) % M, (z[0][0] * z[0][1] + z[0][1] * z[1][1]) % M],
               [(z[1][0] * z[0][0] + z[1][1] * z[1][0]) % M, (z[1][0] * z[0][1] + z[1][1] * z[1][1]) % M]]
          t /= 2
        end
        (3 * y[0][0] + 2 * y[0][1]) % M
      end
  k = d
  b = x
  a = 1
  while k > 0
    if k % 2 == 1
      a = (a * b) % M
    end
    b = b**2 % M
    k /= 2
  end
  a
}.inject(1) {|memo, item| (memo * item) % M}
puts ans