description: Theofanis really likes sequences of positive integers, thus his teacher (Yeltsa Kcir) gave him a problem about a sequence that consists of only special numbers.
  
  Let's call a positive number special if it can be written as a sum of different non-negative powers of n. For example, for n = 4 number 17 is special, because it can be written as 4^0 + 4^2 = 1 + 16 = 17, but 9 is not.
  
  Theofanis asks you to help him find the k-th special number if they are sorted in increasing order. Since this number may be too large, output it modulo 10^9+7.
  
  Input
  
  The first line contains a single integer t (1 ≤ t ≤ 10^4) — the number of test cases.
  
  The first and only line of each test case contains two integers n and k (2 ≤ n ≤ 10^9; 1 ≤ k ≤ 10^9).
  
  Output
  
  For each test case, print one integer — the k-th special number in increasing order modulo 10^9+7.
  
  Example
  
  Input
  
  
  3
  3 4
  2 12
  105 564
  
  
  Output
  
  
  9
  12
  3595374
  
  Note
  
  For n = 3 the sequence is [1,3,4,9...]
solution: from collections import Counter, defaultdict, deque
  import bisect, heapq
  from sys import stdin, stdout
  from itertools import repeat
  import math
  
  
  def inp(force_list=False):
      re = map(int, raw_input().split())
      if len(re) == 1 and not force_list:
          return re[0]
      return re
  
  def inst():
      return raw_input().strip()
  
  def gcd(x, y):
     while(y):
         x, y = y, x % y
     return x
  
  mod = int(1e9+7)
  
  def qmod(a, b):
      res = 1
      while b:
          if b&1:
              res = (res*a)%mod
          b >>= 1
          a = (a*a)%mod
      return res
  
  def inv(a):
      return qmod(a, mod-2)
  
  
  def my_main():
      kase = inp()
      pans = []
      for ka in range(kase):
          # print 'Case #%d: ' % (ka+1),
          n, k = inp()
          ans = [0]
          def kth(kk):
              if not kk:
                  return
              if kk==1:
                  ans[0] += 1
                  return
              per = 1
              now = 1
              for i in range(2, 40):
                  if per*2 > kk:
                      ans[0] += now
                      kth(kk - per)
                      break
                  per *= 2
                  now *= n
                  now %= mod
          kth(k)
          pans.append(str(ans[0]%mod))
      print '\n'.join(pans)
  
  my_main()
  