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: //package codeforces;
  
  import java.io.*;
  import java.util.*;
  
  public class ProblemB {
      private final static FastScanner scanner = new FastScanner();
      private final static long M = 1000000007L;
  
      public static void main(String[] args) throws IOException {
          int n = scanner.nextInt();
          for (int i = 0; i < n; i++) {
              solve();
          }
  //        solve();
      }
  
      public static void solve() {
          long n = scanner.nextLong();
          long k = scanner.nextLong();
  
          long ans = 0;
          for (int i = 0; i < 63; i++) {
              if((k &(1L << i)) != 0){
                  ans = (ans + moduloPower(n, i, M)) % M;
              }
          }
          System.out.println(ans);
      }
  
  //    public static void solve() {
  //        long n = scanner.nextLong();
  //        long k = scanner.nextLong();
  //        List<Long> sequence = new ArrayList<>();
  //        int pow = 0;
  //        while (k > 0) {
  //            long res = moduloPower(n, pow, M);
  //            pow++;
  //            sequence.add(res % M);
  //            k--;
  //            if (k == 0) {
  //                System.out.println(sequence.get(sequence.size() - 1));
  //                return;
  //            }
  //            int size = sequence.size();
  //            for (int i = 0; i < size - 1; i++) {
  //                long num = sequence.get(i);
  //                sequence.add((res + num) % M);
  //                k--;
  //                if (k == 0) {
  //                    System.out.println(sequence.get(sequence.size() - 1));
  //                    return;
  //                }
  //            }
  //        }
  //    }
  
      public static long getManhattanDistance(long x1, long y1, long x2, long y2) {
          return Math.abs(x1 - x2) + Math.abs(y1 - y2);
      }
  
      public static long lcm(long number1, long number2) {
          if (number1 == 0 || number2 == 0) {
              return 0;
          }
          long absNumber1 = Math.abs(number1);
          long absNumber2 = Math.abs(number2);
          long absHigherNumber = Math.max(absNumber1, absNumber2);
          long absLowerNumber = Math.min(absNumber1, absNumber2);
          long lcm = absHigherNumber;
          while (lcm % absLowerNumber != 0) {
              lcm += absHigherNumber;
          }
          return lcm;
      }
  
      static void swap(int[] arr, int l, int r) {
          int temp = arr[l];
          arr[l] = arr[r];
          arr[r] = temp;
      }
  
      static void swap(long[] arr, int l, int r) {
          long temp = arr[l];
          arr[l] = arr[r];
          arr[r] = temp;
      }
  
      private static int getTickSize(char[][] mat, int i, int j) {
          if (i < 0 || j < 0 || i >= mat.length || j >= mat[0].length || mat[i][j] == '.') return 0;
          mat[i][j] = '.';
          return Math.min(getTickSize(mat, i - 1, j - 1), getTickSize(mat, i - 1, j + 1));
      }
  
      private static Boolean isSquare(long x) {
          long y = (long) Math.sqrt(x);
          return y * y == x;
      }
  
      private static int getMax(int[] arr) {
          int[] copy = Arrays.copyOf(arr, arr.length);
          Arrays.sort(copy);
          return copy[arr.length - 1];
      }
  
      private static double customLog(double logNumber, double base) {
          return Math.log(logNumber) / Math.log(base);
      }
  
  
      static int checkSim(String n1, String n2, int i, int j) {
          if (i >= n1.length() || j >= n2.length()) return 0;
          if (n1.charAt(i) == n2.charAt(j)) return 1 + checkSim(n1, n2, i + 1, j + 1);
          return checkSim(n1, n2, i + 1, j);
      }
  
      static int computeXOR(int n) {
          if (n % 4 == 0)
              return n;
          if (n % 4 == 1)
              return 1;
          if (n % 4 == 2)
              return n + 1;
          return 0;
      }
  
      static boolean isPowerOfTwo(long n) {
          if (n == 0)
              return false;
  
          double v = Math.log(n) / Math.log(2);
          return (long) (Math.ceil(v)) == (long) (Math.floor(v));
      }
  
      static boolean isPrime(int n) {
          if (n <= 1)
              return false;
  
          else if (n == 2)
              return true;
  
          else if (n % 2 == 0)
              return false;
  
          for (int i = 3; i <= Math.sqrt(n); i += 2) {
              if (n % i == 0)
                  return false;
          }
          return true;
      }
  
      static boolean checkSorted(int[] arr) {
          for (int i = 1; i < arr.length; i++) {
              if (arr[i - 1] > arr[i]) return false;
          }
          return true;
      }
  
      static void print(int from, int to) {
          if (from <= to) {
              for (int i = from; i <= to; i++) {
                  System.out.print(i + " ");
              }
          } else {
              System.out.print(from + " ");
              for (int i = 1; i <= to; i++) {
                  System.out.print(i + " ");
              }
          }
      }
  
      static long moduloMultiplication(long a, long b, long mod) {
          long res = 0;
          a %= mod;
          while (b > 0) {
              if ((b & 1) > 0) {
                  res = (res + a) % mod;
              }
              a = (2 * a) % mod;
              b >>= 1;
          }
          return res;
      }
  
      static long moduloPower(long x, long y, long p) {
          long res = 1L;
          x = x % p;
          while (y > 0) {
              if ((y & 1) > 0)
                  res = (res * x) % p;
  
              y = y >> 1;
              x = (x * x) % p;
          }
          return res % p;
      }
  
      static int lowerBound(long a[], long x) { // x is the target value or key
          int l = -1, r = a.length;
          while (l + 1 < r) {
              int m = (l + r) >>> 1;
              if (a[m] >= x) r = m;
              else l = m;
          }
          return r;
      }
  
      static int upperBound(long a[], long x) {// x is the key or target value
          int l = -1, r = a.length;
          while (l + 1 < r) {
              int m = (l + r) >>> 1L;
              if (a[m] <= x) l = m;
              else r = m;
          }
          return l + 1;
      }
  
      static long upperBound(long[] arr, int start, int end, long k) {
          int N = end;
          while (start < end) {
              int mid = start + (end - start) / 2;
              if (k >= arr[mid]) {
                  start = mid + 1;
              } else {
                  end = mid;
              }
          }
          if (start < N && arr[start] <= k) {
              start++;
          }
          return start;
      }
  
      static long lowerBound(long[] arr, int start, int end, long k) {
          int N = end;
          while (start < end) {
              int mid = start + (end - start) / 2;
              if (k <= arr[mid]) {
                  end = mid;
              } else {
                  start = mid + 1;
              }
          }
          if (start < N && arr[start] < k) {
              start++;
          }
          return start;
      }
  
      static int getDistance(int x1, int y1, int x2, int y2) {
          return Math.abs(x1 - x2) + Math.abs(y1 - y2);
      }
  
      static int sumOfNNaturalNumbers(int n) {
          return (n * (n + 1)) / 2;
      }
  
      static long sumOfNNaturalNumbers(long n) {
          return (n * (n + 1)) / 2;
      }
  
      static int gcd(int a, int b) {
          if (b == 0)
              return a;
          return gcd(b, a % b);
      }
  
  
      static class FastScanner {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer("");
  
          String next() {
              while (!st.hasMoreTokens())
                  try {
                      st = new StringTokenizer(br.readLine());
                  } catch (IOException e) {
                      e.printStackTrace();
                  }
              return st.nextToken();
          }
  
          int nextInt() {
              return Integer.parseInt(next());
          }
  
          int[] readArray(int n) {
              int[] a = new int[n];
              for (int i = 0; i < n; i++) a[i] = nextInt();
              return a;
          }
  
          long nextLong() {
              return Long.parseLong(next());
          }
      }
  }