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.BufferedReader;
      import java.io.FileInputStream;
      import java.io.FileNotFoundException;
      import java.io.IOException;
      import java.io.InputStreamReader;
      import java.util.*;
      import java.util.concurrent.LinkedBlockingDeque;
  
      import javax.print.attribute.HashAttributeSet;
      import javax.swing.JLabel;
  
      import java.io.PrintStream;
                  
                      public class Solution {
  
                          public static boolean Local(){
                              try{ 
                                  return System.getenv("LOCAL_SYS")!=null;
                              }catch(Exception e){
                                  return false;
                              }
                          }   
  
                          public static boolean LOCAL;
  
                          static class FastScanner {
  
                                  BufferedReader br;
                                  StringTokenizer st ;
  
                                  FastScanner(){
                                      br =  new BufferedReader(new InputStreamReader(System.in));
                                      st = new StringTokenizer("");
                                  }
  
                                  FastScanner(String file) {
  
                                      try{
                                          br =  new BufferedReader(new InputStreamReader(new FileInputStream(file)));
                                          st = new StringTokenizer("");
                                      }catch(FileNotFoundException e) {
                                          // TODO Auto-generated catch block
                                          System.out.println("file not found");
                                          e.printStackTrace();
                                      }
                                      
                                  }
                                  
  
                                  String next() {
                                      while (!st.hasMoreTokens())
                                          try {
                                              st = new StringTokenizer(br.readLine());
                                          } catch (IOException e) {
                                          }
                                      return st.nextToken();
                                  }
  
                                  int nextInt() {
                                      return Integer.parseInt(next());
                                  }
  
                                  long nextLong() {
                                      return Long.parseLong(next());
                                  }
                                  String readLine() throws IOException{
                                      return br.readLine();
                                  }
                              }
                                                  
                          static class Pair<T,X> {
  
                              T first;
                              X second;
                              
                              Pair(T first,X second){
                                  this.first = first;
                                  this.second = second;
                              }
  
                              @Override
                              public int hashCode(){
                                  return Objects.hash(first,second);
                              }
  
                              @Override
                              public boolean equals(Object obj){
                                  return obj.hashCode() == this.hashCode();
                              }
  
                          }
  
                      
                      static PrintStream debug = null;
  
                      static long mod = (long)(Math.pow(10,9) + 7); 
                      
  
                      public static void main(String[] args) throws Exception {
                          
                          FastScanner s = new FastScanner();
  
                          LOCAL = Local();
  
                          
                          if(LOCAL){
                              s = new FastScanner("src/input.txt");
                              PrintStream o = new PrintStream("src/sampleout.txt");
                              debug = new PrintStream("src/debug.txt");
                              System.setOut(o);
                          }
  
                          long mod = 1000000007;
                          int tcr =  s.nextInt();     
                      
                          StringBuilder sb = new StringBuilder();
  
                      
                          for(int tc=0;tc<tcr;tc++){
                              
                              int n = s.nextInt();
                              
                              int k = s.nextInt();
  
                              // int pow = 0;
  
                              // int val = 0;
  
                              // while(val < k){
                              //     val += (Math.pow(2,pow));
                              //     if(val >= k){break;}
                              //     pow++;
                              // }
  
                          //  println(val+"@"+pow);
                          
                              // val -= Math.pow(2,pow);
  
                              // int rem =  k - val - 1;
  
                      
  
                              // List<Long> list = new ArrayList<>();
                              // int pw = 1;
                          //     list.add(1l);
                          //     while(list.size() < rem){
                          //         int curr_size = list.size();
                          //         list.add(modpow(n,pw, mod));
                          //         for(int i=0;i<curr_size;i++){
                          //             list.add((modpow(n,pw, mod) + list.get(i))%mod);
                          //         }
                          //         pw++;
                          //     }
  
                          //     long curr = modpow(n, pow, mod);
  
                          //    // println(curr+"--");
                          //     if((rem) > 0){
                          //         curr += list.get(rem - 1);
                          //     }
  
                          //     dbg(debug,list);
  
                               long ans = solve(n,k); 
  
                              sb.append((ans%mod)+"\n");
  
  
  
  
                          }
  
  
                          print(sb.toString());
                      }
  
                      public static long solve(int n,int k){
                          int pow = 0;
  
                          int val = 0;
  
                          while(val < k){
                              val += (Math.pow(2,pow));
                              if(val >= k){break;}
                              pow++;
                          }
  
                      //  println(val+"@"+pow);
                      
                          val -= Math.pow(2,pow);
  
                          int rem =  k - val - 1;
  
                          if(rem == 0){
                              return modpow(n, pow, mod);
                          }
  
                          return (modpow(n, pow, mod) + solve(n,rem))%mod;
                      }
  
                      public static long ncr(int n,int r,long fact[]){
                          if(r==0){return 1l;}
                          long ans = fact[n];
                          long denom = mulmod(fact[r], fact[n-r], mod);
                          ans = mulmod(ans,modpow(denom,mod-2, mod),mod);
                          return ans;
                      }
  
                      public static List<long[]> prime_factors(long n){
                  
                          List<long[]> list = new ArrayList<>();
                          
                          for(long i=2;i<=(Math.sqrt(n));i++){
                  
                              if(n % i == 0){
                                  
                                  int cnt = 0;
                                  
                                  while( (n % i) == 0){
                                      n = n/i;
                                      cnt++;
                                      
                                  }
                  
                                  list.add(new long[]{i,cnt});
                              }
                          }
  
                  
                          if(n!=1){
                              list.add(new long[]{n,1l});
                          }
                  
                          return list;
                  
                      }
  
                      public static boolean check(int arr[]){
                          for(int i=1;i<arr.length;i++){
                              if(arr[i] < arr[i-1]){
                                  return false;
                              }
                          }
                          return true;
                      }
  
                  
                      public static boolean inRange(int r1,int r2,int val){
                          return ((val >= r1) && (val <= r2));
                      }
  
                      static int len(long num){
                          return Long.toString(num).length();
                      }
  
                      static long mulmod(long a, long b,long mod)
                      {
  
                          return (a*b)%mod;
                          
                          // long ans = 0l;
                          
                          // while(b > 0l){
                          //     long curr = (b & 1l);
                          //     if(curr == 1l){
                          //         ans = ((ans % mod) + a) % mod;
                          //     }
                              
                          //     a = (a + a) % mod;
  
                          //     b = b >> 1;
                          // }
  
                          // return ans;
                      }
  
  
                      public static void dbg(PrintStream ps,Object... o) throws Exception{
                          if(ps == null){
                              return;
                          }
                          Debug.dbg(ps,o);
                      }
  
                      public static long modpow(long num,long pow,long mod){
  
                          long val = num;
                          long ans = 1l;
  
                          while(pow > 0l){
                              
                              long bit = pow & 1l;
  
                              if(bit == 1){
                                  ans = (ans * (val%mod))%mod;
                              }
  
                              val = (val * val) % mod;
                              pow = pow >> 1;
                          }
  
                          return ans;
  
                      }
  
                      public static char get(int n){
                          return (char)('a' + n);
                      }
  
                      public static long[] sort(long arr[]){
                          List<Long> list = new ArrayList<>();
                          for(long n : arr){list.add(n);}
                          Collections.sort(list);
                          for(int i=0;i<arr.length;i++){
                              arr[i] = list.get(i);
                          }
                          return arr;
                      }
  
                      public static int[] sort(int arr[]){
                          List<Integer> list = new ArrayList<>();
                          for(int n : arr){list.add(n);}
                          Collections.sort(list);
                          for(int i=0;i<arr.length;i++){
                              arr[i] = list.get(i);
                          }
                          return arr;
                      }
  
                      // return the (index + 1)
                      // where index is the pos of just smaller element
                      // i.e count of elemets strictly less than num
                      public static int justSmaller(long arr[],long num){
                          //  System.out.println(num+"@");
                          int st = 0;
                          int e = arr.length - 1;
                  
                          int ans = -1;
                  
                          while(st <= e){
                  
                              int mid = (st + e)/2;
                  
                              if(arr[mid] >= num){
                                  e = mid - 1;
                              }else{
                                  ans = mid;
                                  st = mid + 1;
                              }
                  
                          }
                  
                  
                          return ans + 1;
                  
                      }
                      public static int justSmaller(int arr[],int num){
                          //  System.out.println(num+"@");
                          int st = 0;
                          int e = arr.length - 1;
                  
                          int ans = -1;
                  
                          while(st <= e){
                  
                              int mid = (st + e)/2;
                  
                              if(arr[mid] >= num){
                                  e = mid - 1;
                              }else{
                                  ans = mid;
                                  st = mid + 1;
                              }
                  
                          }
                  
                  
                          return ans + 1;
                  
                      }
                      
                      //return (index of just greater element)
                      //count of elements smaller than or equal to num
  
                      public static int justGreater(long arr[],long num){
                          int st = 0;
                          int e = arr.length - 1;
                  
                          int ans = arr.length;
                  
                          while(st <= e){
                              
                              int mid = (st + e)/2;
                  
                              if(arr[mid] <= num){
                                  st = mid + 1;
                              }else{
                                  ans = mid;
                                  e = mid - 1;
                              }
                          }
                  
                          return ans;
                  
                      }
  
                      public static int justGreater(int arr[],int num){
                          int st = 0;
                          int e = arr.length - 1;
                  
                          int ans = arr.length;
                  
                          while(st <= e){
                              
                              int mid = (st + e)/2;
                  
                              if(arr[mid] <= num){
                                  st = mid + 1;
                              }else{
                                  ans = mid;
                                  e = mid - 1;
                              }
                          }
                  
                          return ans;
                  
                      }
                  
                      
  
                      public static void println(Object obj){
                          System.out.println(obj.toString());
                      }
  
                      public static void print(Object obj){
                          System.out.print(obj.toString());
                      }
  
                      public static int gcd(int a,int b){
                          if(b == 0){return a;}
                          return gcd(b,a%b);
                      }
  
                      public static long gcd(long a,long b){
                          if(b == 0l){
                              return a;
                          }
  
                          return gcd(b,a%b);
                      }
  
                      public static int find(int parent[],int v){
                          if(parent[v] == v){
                              return v;
                          }
                          
                          return parent[v] = find(parent, parent[v]);
                      }
  
                  
  
                      public static List<Integer> sieve(){
                      
                              List<Integer> prime = new ArrayList<>();
  
                              int arr[] = new int[1000001];
  
                          Arrays.fill(arr,1);
  
                          arr[1] = 0;
                          arr[2] = 1;
  
                          for(int i=2;i<1000001;i++){
                              
                              if(arr[i] == 1){
                                  
                                  prime.add(i);
  
                                  for(long j = (i*1l*i);j<1000001;j+=i){
                                      arr[(int)j] = 0;
                                  }
                              }
                          }
  
                          return prime;
                      }
  
                      static boolean isPower(long n,long a){
                          
                          long log = (long)(Math.log(n)/Math.log(a));
  
                          long power = (long)Math.pow(a,log);
  
                          if(power == n){return true;}
  
                          return false;
                      }
  
  
                      private static int mergeAndCount(int[] arr, int l,int m, int r)
                      {
  
                          // Left subarray
                          int[] left =  Arrays.copyOfRange(arr, l, m + 1);
  
                          // Right subarray
                          int[] right = Arrays.copyOfRange(arr, m + 1, r + 1);
  
                          int i = 0, j = 0, k = l, swaps = 0;
  
                          while (i < left.length && j < right.length) {
                              if (left[i] <= right[j])
                                  arr[k++] = left[i++];
                              else {
                                  arr[k++] = right[j++];
                                  swaps += (m + 1) - (l + i);
                              }
                          }
                          while (i < left.length)
                              arr[k++] = left[i++];
                          while (j < right.length)
                              arr[k++] = right[j++];
                          return swaps;
                      }
  
                      // Merge sort function
                      private static int mergeSortAndCount(int[] arr, int l,int r)
                      {
  
                          // Keeps track of the inversion count at a
                          // particular node of the recursion tree
                          int count = 0;
  
                          if (l < r) {
                              int m = (l + r) / 2;
  
                              // Total inversion count = left subarray count
                              // + right subarray count + merge count
  
                              // Left subarray count
                              count += mergeSortAndCount(arr, l, m);
  
                              // Right subarray count
                              count += mergeSortAndCount(arr, m + 1, r);
  
                              // Merge count
                              count += mergeAndCount(arr, l, m, r);
                          }
  
                          return count;
                      }
  
                      static class Debug{
                          //change to System.getProperty("ONLINE_JUDGE")==null; for CodeForces
                          public static final boolean LOCAL = System.getProperty("ONLINE_JUDGE")==null;
  
                          
  
                          private static <T> String ts(T t) {
                              if(t==null) {
                                  return "null";
                              }
                              try {
                                  return ts((Iterable) t);
                              }catch(ClassCastException e) {
                                  if(t instanceof int[]) {
                                      String s = Arrays.toString((int[]) t);
                                      return "{"+s.substring(1, s.length()-1)+"}\n";
                                  }else if(t instanceof long[]) {
                                      String s = Arrays.toString((long[]) t);
                                      return "{"+s.substring(1, s.length()-1)+"}\n";
                                  }else if(t instanceof char[]) {
                                      String s = Arrays.toString((char[]) t);
                                      return "{"+s.substring(1, s.length()-1)+"}\n";
                                  }else if(t instanceof double[]) {
                                      String s = Arrays.toString((double[]) t);
                                      return "{"+s.substring(1, s.length()-1)+"}\n";
                                  }else if(t instanceof boolean[]) {
                                      String s = Arrays.toString((boolean[]) t);
                                      return "{"+s.substring(1, s.length()-1)+"}\n";
                                  }
                                  try {
                                      return ts((Object[]) t);
                                  }catch(ClassCastException e1) {
                                      return t.toString();
                                  }
                              }
                          }
                          private static <T> String ts(T[] arr) {
                              StringBuilder ret = new StringBuilder();
                              ret.append("{");
                              boolean first = true;
                              for(T t: arr) {
                                  if(!first) {
                                      ret.append(", ");
                                  }
                                  first = false;
                                  ret.append(ts(t));
                              }
                              ret.append("}");
                              return ret.toString();
                          }
                          private static <T> String ts(Iterable<T> iter) {
                              StringBuilder ret = new StringBuilder();
                              ret.append("{");
                              boolean first = true;
                              for(T t: iter) {
                                  if(!first) {
                                      ret.append(", ");
                                  }
                                  first = false;
                                  ret.append(ts(t));
                              }
                              ret.append("}");
                              return ret.toString();
                          }
                          public static void dbg(PrintStream ps,Object... o) throws Exception {
                              if(LOCAL) {
                                  System.setErr(ps);
                                  System.err.print("Line #"+Thread.currentThread().getStackTrace()[2].getLineNumber()+": [");
                                  for(int i = 0; i<o.length; i++) {
                                      if(i!=0) {
                                          System.err.print(", ");
                                      }
                                      System.err.print(ts(o[i]));
                                  }
                                  System.err.println("]");
                              }
                          }
                      }
  
              }
  
  
              