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: import java.io.*;
  import java.util.*;
  
  public class contest {
      static PrintWriter pw;
  
      static public class pair implements Comparable<pair> {
          int x;
          int y;
  
          public pair(int x, int y) {
              this.x = x;
              this.y = y;
          }
  
  
          public int compareTo(pair o) {
              if (x - o.x == 0)
                  return y - o.y;
              return x - o.x;
          }
      }
  
      public static boolean isprefix(String base, String pref) {
          int m = pref.length();
          for (int i = 0; i < m; i++) {
              if (base.charAt(i) != pref.charAt(i)) {
                  return false;
              }
  
          }
          return true;
      }
  
      static TreeSet<Integer>[] adj;
      static boolean[] vis;
      static boolean fin = false;
  
      public static void dfs(int u) {
          pw.print((u + 1) + " ");
          vis[u] = true;
          boolean one = false;
          for (int v : adj[u]) {
  //            if(v==0) {
  //                pw.println(1);
  //                fin=true;
  //            }
              if (!fin & !vis[v]) {
                  dfs(v);
                  pw.print((u + 1) + " ");
              }
          }
          return;
      }
  
      static boolean[][] Matrix;
      static int n, m;
  
      public static int dp(int i, int j) {
          if (i == n && j == m)
              return 0;
          if (memo[i][j] != -1)
              return memo[i][j];
          int ans = 0;
          //up
          if (i < n && Matrix[i + 1][j])
              ans = Math.min(ans, dp(i + 1, j));
  
          if (i > 0 && Matrix[i - 1][j])
              ans = Math.min(ans, dp(i - 1, j));
          if (j < m && Matrix[i][j + 1])
              ans = Math.min(ans, dp(i, j + 1));
  
          if (j > 0 && Matrix[i][j - 1])
              ans = Math.min(ans, dp(i, j - 1));
  
          ans = 1 + Math.min(ans, dp(i + 2, j + 2));
          ans = 1 + Math.min(ans, dp(i - 2, j + 2));
          ans = 1 + Math.min(ans, dp(i + 2, j - 2));
          ans = 1 + Math.min(ans, dp(i - 2, j - 2));
  
          ans = 1 + Math.min(ans, dp(i + 1, j + 2));
          ans = 1 + Math.min(ans, dp(i - 1, j + 2));
          ans = 1 + Math.min(ans, dp(i + 1, j - 2));
          ans = 1 + Math.min(ans, dp(i - 1, j - 2));
  
  
          ans = 1 + Math.min(ans, dp(i + 2, j + 1));
          ans = 1 + Math.min(ans, dp(i - 2, j + 1));
          ans = 1 + Math.min(ans, dp(i + 2, j - 1));
          ans = 1 + Math.min(ans, dp(i - 2, j - 1));
          return memo[i][j] = ans;
      }
  
      static int[][] memo;
      static long mod = (long) (1e9 + 7);
  
      public static long modPow(int base, int pow) {
          long ans = 1;
          while (pow > 0) {
              if ((pow & 1) != 0) {
                  ans *= base;
                  ans %= mod;
              }
  
              base *= base;
              base %= mod;
              pow >>= 1;
  
          }
          return ans % mod;
      }
  
      static int power(int x, int y, int p) {
          int res = 1; // Initialize result
  
          x = x % p; // Update x if it is more than or
          // equal to p
  
          if (x == 0)
              return 0; // In case x is divisible by p;
  
          while (y > 0) {
  
              // If y is odd, multiply x with result
              if ((y & 1) != 0)
                  res = (res * x) % p;
  
              // y must be even now
              y = y >> 1; // y = y/2
              x = (x * x) % p;
          }
          return res;
      }
  
  
      public static void main(String[] args) throws Exception {
          Scanner sc = new Scanner(System.in);
          pw = new PrintWriter(System.out);
          int t = sc.nextInt();
          while (t-- > 0) {
              long n = sc.nextInt();
              long k = sc.nextInt();
              long ans = 0;
              long cnt = 1;
              for (int i = 0; i < 32; i++) {
                  if (((1 << i) & k) != 0)
                      ans += cnt;
                  ans %= mod;
                  cnt *= n;
                  cnt %= mod;
              }
              pw.println(ans);
          }
          pw.close();
  
      }
  
  
      public static int ciel(int u, int v) {
          if (u % v == 0)
              return u / v;
          return (u / v) + 1;
      }
  
      public static class Scanner {
          StringTokenizer st;
          BufferedReader br;
  
          public Scanner(InputStream s) {
              br = new BufferedReader(new InputStreamReader(s));
          }
  
          public String next() throws IOException {
              while (st == null || !st.hasMoreTokens())
                  st = new StringTokenizer(br.readLine());
              return st.nextToken();
          }
  
          public int nextInt() throws IOException {
              return Integer.parseInt(next());
          }
  
          public long nextLong() throws IOException {
              return Long.parseLong(next());
          }
  
          public String nextLine() throws IOException {
              return br.readLine();
          }
  
          public double nextDouble() throws IOException {
              String x = next();
              StringBuilder sb = new StringBuilder("0");
              double res = 0, f = 1;
              boolean dec = false, neg = false;
              int start = 0;
              if (x.charAt(0) == '-') {
                  neg = true;
                  start++;
              }
              for (int i = start; i < x.length(); i++)
                  if (x.charAt(i) == '.') {
                      res = Long.parseLong(sb.toString());
                      sb = new StringBuilder("0");
                      dec = true;
                  } else {
                      sb.append(x.charAt(i));
                      if (dec)
                          f *= 10;
                  }
              res += Long.parseLong(sb.toString()) / f;
              return res * (neg ? -1 : 1);
          }
  
          public boolean ready() throws IOException, IOException {
              return br.ready();
          }
  
      }
  }
  