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
        f1, f2, f3, f4 = 1, 1, 1, 0
        g1, g2, g3, g4 = 1, 0, 1, 0
        while t > 0
          if t % 2 == 1
            h1 = (g1 * f1 + g2 * f3) % M
            h2 = (g1 * f2 + g2 * f4) % M
            h3 = (g3 * f1 + g4 * f3) % M
            h4 = (g3 * f2 + g4 * f4) % M
            g1 = h1
            g2 = h2
            g3 = h3
            g4 = h4
          end
          h1 = (f1 * f1 + f2 * f3) % M
          h2 = (f1 * f2 + f2 * f4) % M
          h3 = (f3 * f1 + f4 * f3) % M
          h4 = (f3 * f2 + f4 * f4) % M
          f1 = h1
          f2 = h2
          f3 = h3
          f4 = h4
          t /= 2
        end
        (3 * g1 + 2 * g2) % 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